# Sharky Surfing

## Problem Description

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 Format

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 Format

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

## Sample #1

### Sample Input #1

```
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
```

### Sample Output #1

```
4
-1
1
2
```

## Hint

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.

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: data structures, greedy, two pointers
Difficulty: 1300