Mualani rất thích đi lướt sóng trên chiêc ván cá mập của cô ấy. Vì thế hôm nay, cô quyết định rủ bạn tham gia lướt sóng ở phía Nam Natlan.

Chặng lướt sóng mà Mualani dẫn bạn tới có thể được biểu diễn bới một đường thẳng. Mualani sẽ bắt đầu từ vị trí 1 và chặng sẽ kết thúc ở vị trí ~L~.

Khi Mualani đang ở vị trí ~x~ và có sức nhảy ~k~, cô có thể nhảy từ vị trí ~x~ đến bất kỳ vị trí nào trong khoảng ~[x,x+k]~. Ban đầu, cô có sức nhảy là ~1~.

Chặng lướt này không bằng phẳng, có ~N~ chướng ngại vật ở trên chặng, mỗi chướng ngại vật được mô tả bởi một khoảng ~[l, r]~

Trên chặng còn có ~M~ bình tăng sức mạnh, bình tăng sức mạnh thứ ~i~ ở vị trí ~x_i~ có giá trị ~v_i~. Khi Mualani gặp chúng, cô có lựa chọn là uống bình tăng sức mạnh để tăng sức nháy thêm một lượng ~v_i~ hoặc bỏ qua chúng. Có thể nhiều bình tại cùng một vị trí nhưng không có bình nào ở trong vùng chướng ngại vật.

Vậy Mualani cần nhặt ít nhất bao nhiêu bình để có thể hoàn thành được chặng lướt sóng này?

Input

Dòng đầu tiên chưa một số nguyên ~T~: số test case

Dòng đầu tiên của test case chứa 3 số nguyên: ~N~, ~M~, ~L~: số chướng ngại vật, số bình tăng sức mạnh và độ dài chặng

~N~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~l_i~ và ~r_i~, mô tả chướng ngại vật thứ ~i~

~M~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~x_i~ và ~v_i~, mô tả bình tăng sức mạnh thứ ~i~.

Output

In ra ~T~ dòng là kết quả của từng bộ test, nếu Mualani không thể hoàn thành chặng, in ra ~-1~.

Giới hạn

~1 <= T <= 10^4~

~1 <= N,M <= 2*10^5~

~3 <= L <= 10^9~

~1 <= x_i <= 10^9~, bình tăng sức mạnh nằm ở ô không có chướng ngại vật

~1 <= v_i <= 10^9~

Đảm bảo giới hạn của N và M trong các test case không quá ~2*10^5~

Test mẫu

Input

2
2 5 50
7 14
30 40
2 2
3 1
3 5
18 2
22 32
4 3 50
4 6
15 18
20 26
34 38
1 2
8 2
10 2

Output

4
-1