Để chuẩn bị cho chuyến đi chơi giáng sinh ~n~ ngày ~n~ đêm của mình với Chủ tịch Miyuki, Kaguya đã xem dự báo thời tiết trên website http://vnoi.info/ của cơ quan dự báo khí tượng VNOI, họ cho biết trong ~n~ ngày tới, nhiệt độ có thể lên tới ~10^5~ độ ~C~!!!! Chính xác hơn là ngày thứ ~i~ sẽ có nhiệt độ là một số thực không nhỏ hơn ~t_i~ và không lớn hơn ~10^5~. Đúng là một mùa đông không lạnh!!! Có thể bạn đang thắc mắc tại sao nhiệt đó có thể lớn đến thế, đó là do hiện tượng nóng lên toàn cầu.

Kaguya là một người sợ nhiệt độ cao nên sau khi nhận được thông tin này bạn đã quyết định sẽ đặt mua một số món đồ bảo hộ để bảo vệ bản thân mình. Nắm bắt được tình hình này, hãng sản xuất đồ bảo hộ CoolMac đã tung ra thị trường ~m~ loại đồ bảo hộ có thể chống chịu được nhiệt độ cao, thông tin thêm là tất cả đều được sản xuất ~100~% tại Việt Nam. Phía CoolMac cho biết, loại đồ thứ ~i~ sẽ chịu được nhiệt độ từ ~L_i~ tới ~R_i~ và đều được bán với giá là ~1~ đồng.

Tuy vậy, do không biết chính xác được nhiệt độ của từng ngày nên Kaguya phải mua rất nhiều loại đồ để chuẩn bị mọi trường hợp có thể xảy ra. Chẳng hạn, nếu như thông báo của VNOI về nhiệt độ của ngày ~1~ là ~[100, 10^5]~ và CoolMac chỉ bán 2 loại đồ với mức chống chịu là ~[1, 200]~ và ~[150, 10^5]~ thì Kaguya phải mua cả 2 loại đồ này để để phòng. Nếu chỉ mua loại đồ thứ hai và nhiệt độ rơi vào khoảng ~[100, 150)~ thì Kaguya sẽ không có đồ bảo hộ phù hợp để mặc để đi chơi noel.

Dù là con gái của gia tộc giàu có bậc nhất Nhật bản nhưng Kaguya có lối sống rất tiết kiệm, do đó thay vì mua hết tất cả món đồ từ CoolMac (hoặc là mua cả CoolMac luôn) thì Kaguya muốn tối thiểu số lượng đồ bảo hộ cần mua. Do đang bận lên kế hoạch đi chơi với chủ tịch, Kaguya đã nhờ một con cá nóc giấu tên đem câu hỏi này vào đề thi VNOI Online 2021 để nhờ các bạn thí sinh trả lời.

Input

• Dòng đầu tiên chứa số nguyên dương ~m~ (~1 \le m \le 10^5~) là số lượng loại đồ bảo hộ mà phía CoolMac tung ra thị trường.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên ~L_i~ và ~R_i~ (~0 \le L_i \le R_i \le 10^5~) biểu thị cho khả năng chống chịu của món đồ thứ ~i~.
• Dòng tiếp theo chứa số nguyên dương ~n~ (~1 \le n \le 10^5~) chính là số lượng ngày mà VNOI đã dự đoán nhiệt độ.
• Dòng tiếp theo chứa ~n~ số nguyên không âm, số thứ ~i~ là ~t_i~ (~0 \le t_i \le 10^5~) -- nhiệt độ thấp nhất của ngày ~i~.

Output

In ra một số nguyên duy nhất là số lượng đồ bảo hộ ít nhất mà Kaguya cần mua để có thể đảm bảo an toàn của mình trong mọi trường hợp. Nếu như không có cách nào đảm bảo, in ra ~-1~.

Giới hạn

• ~30~% số điểm có ~1 \le n \le 10~ và ~1 \le m \le 16~
• ~30~% số điểm tiếp theo có ~1 \le n \le 3000~ và ~1 \le m \le 3000~
• ~40~% số điểm còn lại không có giới hạn gì thêm

Sample Input 1

3
250 100000
150 200
10 300
2
1000 200

Sample Output 1

2

Sample Input 2

2
250 100000
90 248
1
100

Sample Output 2

-1

Note

Ở ví dụ đầu tiên, Kaguya sẽ mua 2 đồ bảo hộ chịu lần lượt là ~[250; 100\;000]~ và ~[10; 300]~.

Ở ví dụ thứ 2, dù có mua cách nào cũng không có gì để mặc ở trường hợp nhiệt độ ngày thứ 2 là ~249~ độ.