D. Sharky Surfing
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mualani loves surfing on her sharky surfboard!

Mualani's surf path can be modeled by a number line. She starts at position $$$1$$$, and the path ends at position $$$L$$$. When she is at position $$$x$$$ with a jump power of $$$k$$$, she can jump to any integer position in the interval $$$[x, x+k]$$$. Initially, her jump power is $$$1$$$.

However, her surf path isn't completely smooth. There are $$$n$$$ hurdles on her path. Each hurdle is represented by an interval $$$[l, r]$$$, meaning she cannot jump to any position in the interval $$$[l, r]$$$.

There are also $$$m$$$ power-ups at certain positions on the path. Power-up $$$i$$$ is located at position $$$x_i$$$ and has a value of $$$v_i$$$. When Mualani is at position $$$x_i$$$, she has the option to collect the power-up to increase her jump power by $$$v_i$$$. There may be multiple power-ups at the same position. When she is at a position with some power-ups, she may choose to take or ignore each individual power-up. No power-up is in the interval of any hurdle.

What is the minimum number of power-ups she must collect to reach position $$$L$$$ to finish the path? If it is not possible to finish the surf path, output $$$-1$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$L$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 3 \leq L \leq 10^9$$$) — the number of hurdles, the number of power-ups, and the position of the end.

The following $$$n$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$2 \leq l_i \leq r_i \leq L-1$$$) — the bounds of the interval for the $$$i$$$'th hurdle. It is guaranteed that $$$r_i + 1 < l_{i+1}$$$ for all $$$1 \leq i < n$$$ (i.e. all hurdles are non-overlapping, sorted by increasing positions, and the end point of a previous hurdle is not consecutive with the start point of the next hurdle).

The following $$$m$$$ lines contain two integers $$$x_i$$$ and $$$v_i$$$ ($$$1 \leq x_i, v_i \leq L$$$) — the position and the value for the $$$i$$$'th power-up. There may be multiple power-ups with the same $$$x$$$. It is guaranteed that $$$x_i \leq x_{i+1}$$$ for all $$$1 \leq i < m$$$ (i.e. the power-ups are sorted by non-decreasing position) and no power-up is in the interval of any hurdle.

It is guaranteed the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the minimum number of power-ups she must collect to reach position $$$L$$$. If it is not possible, output $$$-1$$$.

Example
Input
4
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
1 4 17
10 14
1 6
1 2
1 2
16 9
1 2 10
5 9
2 3
2 2
Output
4
-1
1
2
Note

In the first test case, she can collect power-ups $$$1$$$, $$$2$$$, $$$3$$$, and $$$5$$$ to clear all hurdles.

In the second test case, she cannot jump over the first hurdle.

In the fourth test case, by collecting both power-ups, she can jump over the hurdle.