Муалани любит серфинг на своей акульей доске!
Путь серфинга Муалани можно смоделировать с помощью числовой прямой. Она начинает с позиции \(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\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество усилений, которые она должна собрать, чтобы достичь позиции \(L\). Если это невозможно, выведите \(-1\).
Примечание
В первом наборе входных данных она может собрать усиления \(1\), \(2\), \(3\) и \(5\), чтобы преодолеть все препятствия.
Во втором наборе входных данных она не может перепрыгнуть первое препятствие.
В четвертом наборе входных данных, собрав оба усиления, она сможет перепрыгнуть препятствие.
Примеры
| № | Входные данные | Выходные данные |
|
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
|