Вы играете в компьютерную игру, в которой руководите \(m\) солдатами. У каждого солдата есть своя ловкость \(a_i\).
Уровень, который вы проходите, можно представить как отрезок прямой между точками \(0\) (где вы и ваш отряд изначально) и \(n + 1\) (где находится босс уровня).
Уровень заполнен \(k\) ловушками. Каждая ловушка характеризуется тремя числами \(l_i\), \(r_i\) и \(d_i\). \(l_i\) — точка, в которой расположена ловушка, а \(d_i\) — опасность ловушки: когда солдат с ловкостью меньше \(d_i\) наступает на нее (то есть перемещается в точку \(l_i\)), ловушка сразу же убивает его. К счастью, вы можете разряжать ловушки: если вы дойдете до точки \(r_i\), вы можете разрядить ловушку, и она больше не будет представлять угрозу. На вас ловушки не действуют, только на ваших солдат.
У вас есть \(t\) секунд на прохождение уровня — то есть на то, чтобы вы смогли доставить некоторых солдат к боссу. Перед началом уровня вы выбираете, каких солдат вы будете вести, а какие останутся вне уровня. После этого вам нужно привести всех выбранных солдат к боссу. Для этого вы можете совершать следующие действия:
- если вы находитесь в точке \(x\), вы можете переместиться в \(x + 1\) или в \(x - 1\). Это действие тратит одну секунду;
- если вы находитесь в точке \(x\) и ваш отряд находится в точке \(x\), вы можете переместиться в \(x + 1\) или \(x - 1\) вместе с отрядом за одну секунду. Вы не можете совершать это действие, если оно опасно для солдат (то есть точка, в которую вы перемещаетесь, содержит неразряженную ловушку с величиной \(d_i\) больше ловкости какого-нибудь солдата в отряде). Это действие тратит одну секунду;
- если вы находитесь в точке \(x\) и существует ловушка \(i\) с \(r_i = x\), вы можете разрядить эту ловушку. Это действие не тратит времени.
Обратите внимание, что после каждого действия и ваша координата, и координата вашего отряда — целые числа.
Вы должны выбрать максимальное количество солдат, которых вы сможете привести из точки \(0\) в точку \(n + 1\) не более чем за \(t\) секунд.
Выходные данные
Выведите одно целое число — максимальное количество солдат, которых можно привести к боссу не более чем за \(t\) секунд.
Примечание
В первом примере можно взять с собой солдат с ловкостью \(3\), \(4\) и \(5\). Пройти уровень можно следующим образом:
- пойти в точку \(2\) без отряда;
- разрядить ловушку \(2\);
- пойти в точку \(3\) без отряда;
- разрядить ловушку \(3\);
- пойти в \(0\) без отряда;
- пойти в \(7\) с отрядом.
Весь план можно выполнить за \(13\) секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 4 14
1 2 3 4 5
1 5 2
1 2 5
2 3 5
3 5 3
|
3
|