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$.

见题面 Input 部分

见题面 Output 部分

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.