D. Акулий серфинг
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Муалани любит серфинг на своей акульей доске!

Путь серфинга Муалани можно смоделировать с помощью числовой прямой. Она начинает с позиции $$$1$$$, а путь заканчивается на позиции $$$L$$$. Когда она находится в позиции $$$x$$$ с силой прыжка $$$k$$$, она может прыгнуть в любую целую позицию в интервале $$$[x, x+k]$$$. Изначально ее сила прыжка равна $$$1$$$.

Однако ее путь серфинга не совсем гладкий. На ее пути есть $$$n$$$ препятствий. Каждое препятствие представлено отрезком $$$[l, r]$$$, что означает, что она не может прыгнуть на любую позицию в отрезке $$$[l, r]$$$.

Также на определенных позициях на пути есть $$$m$$$ усилений. Усиление $$$i$$$ расположено на позиции $$$x_i$$$ и имеет значение $$$v_i$$$. Когда Муалани находится на позиции $$$x_i$$$, она может собрать усиление, чтобы увеличить свою силу прыжка на $$$v_i$$$. На одной и той же позиции может быть несколько усилений. Когда она находится на позиции с несколькими усилениями, она может выбрать, взять или игнорировать каждое отдельное усиление. Ни одно усиление не находится в отрезке любого препятствия.

Каково минимальное количество усилений, которые она должна собрать, чтобы достичь позиции $$$L$$$ и завершить путь? Если завершить путь невозможно, выведите $$$-1$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$L$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 3 \leq L \leq 10^9$$$) — количество препятствий, количество усилений и позицию конца.

Следующие $$$n$$$ строк содержат по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$2 \leq l_i \leq r_i \leq L-1$$$) — границы отрезка для $$$i$$$-го препятствия. Гарантируется, что $$$r_i + 1 < l_{i+1}$$$ для всех $$$1 \leq i < n$$$ (т.е. все препятствия не перекрываются, отсортированы по возрастанию позиций, и конец предыдущего препятствия не является последовательным с началом следующего препятствия).

Следующие $$$m$$$ строк содержат по два целых числа $$$x_i$$$ и $$$v_i$$$ ($$$1 \leq x_i, v_i \leq L$$$) — позицию и значение для $$$i$$$-го усиления. На одной и той же позиции $$$x$$$ может быть несколько усилений. Гарантируется, что $$$x_i \leq x_{i+1}$$$ для всех $$$1 \leq i < m$$$ (т.е. усиления отсортированы по неубывания позиции) и ни одно усиление не находится в отрезке любого препятствия.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество усилений, которые она должна собрать, чтобы достичь позиции $$$L$$$. Если это невозможно, выведите $$$-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
Выходные данные
4
-1
1
2
Примечание

В первом наборе входных данных она может собрать усиления $$$1$$$, $$$2$$$, $$$3$$$ и $$$5$$$, чтобы преодолеть все препятствия.

Во втором наборе входных данных она не может перепрыгнуть первое препятствие.

В четвертом наборе входных данных, собрав оба усиления, она сможет перепрыгнуть препятствие.