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 \lt l_{i+1}$$$ for all $$$1 \leq i \lt 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 \lt 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$$$.

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.

Sharky Surfing

Examples