CF2037D Sharky Surfing

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

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

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

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.