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

Вы играете в компьютерную игру, в которой руководите $$$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$$$ секунд.

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

В первой строке записаны четыре целых числа $$$m$$$, $$$n$$$, $$$k$$$ и $$$t$$$ ($$$1 \le m, n, k, t \le 2 \cdot 10^5$$$, $$$n < t$$$) — количество солдат, количество целочисленных точек между вами и боссом, количество ловушек и время на прохождение уровня.

Во второй строке записаны $$$m$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_m$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ — ловкость $$$i$$$-го солдата.

Затем следуют $$$k$$$ строк, описывающих ловушки. В каждой строке записаны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$d_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le d_i \le 2 \cdot 10^5$$$) — местоположение ловушки, точка, из которой ловушку можно разрядить, и опасность ловушки.

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

Выведите одно целое число — максимальное количество солдат, которых можно привести к боссу не более чем за $$$t$$$ секунд.

Пример
Входные данные
5 6 4 14
1 2 3 4 5
1 5 2
1 2 5
2 3 5
3 5 3
Выходные данные
3
Примечание

В первом примере можно взять с собой солдат с ловкостью $$$3$$$, $$$4$$$ и $$$5$$$. Пройти уровень можно следующим образом:

  • пойти в точку $$$2$$$ без отряда;
  • разрядить ловушку $$$2$$$;
  • пойти в точку $$$3$$$ без отряда;
  • разрядить ловушку $$$3$$$;
  • пойти в $$$0$$$ без отряда;
  • пойти в $$$7$$$ с отрядом.

Весь план можно выполнить за $$$13$$$ секунд.