CF1260D.A Game with Traps

You are playing a computer game, where you lead a party of $m$ soldiers. Each soldier is characterised by his agility $a_i$.

The level you are trying to get through can be represented as a straight line segment from point $0$ (where you and your squad is initially located) to point $n + 1$ (where the boss is located).

The level is filled with $k$ traps. Each trap is represented by three numbers $l_i$, $r_i$ and $d_i$. $l_i$ is the location of the trap, and $d_i$ is the danger level of the trap: whenever a soldier with agility lower than $d_i$ steps on a trap (that is, moves to the point $l_i$), he gets instantly killed. Fortunately, you can disarm traps: if you move to the point $r_i$, you disarm this trap, and it no longer poses any danger to your soldiers. Traps don't affect you, only your soldiers.

You have $t$ seconds to complete the level — that is, to bring some soldiers from your squad to the boss. Before the level starts, you choose which soldiers will be coming with you, and which soldiers won't be. After that, you have to bring all of the chosen soldiers to the boss. To do so, you may perform the following actions:

• if your location is $x$, you may move to $x + 1$ or $x - 1$. This action consumes one second;
• if your location is $x$ and the location of your squad is $x$, you may move to $x + 1$ or to $x - 1$ with your squad in one second. You may not perform this action if it puts some soldier in danger (i. e. the point your squad is moving into contains a non-disarmed trap with $d_i$ greater than agility of some soldier from the squad). This action consumes one second;
• if your location is $x$ and there is a trap $i$ with $r_i = x$, you may disarm this trap. This action is done instantly (it consumes no time).

Note that after each action both your coordinate and the coordinate of your squad should be integers.

You have to choose the maximum number of soldiers such that they all can be brought from the point $0$ to the point $n + 1$ (where the boss waits) in no more than $t$ seconds.

你正在玩一款电脑游戏，游戏中你率领一支由 $m$ 名士兵组成的队伍。每名士兵有一个敏捷值 $a_i$。

你当前试图通过的关卡可以表示为一条从点 $0$（你和你的队伍初始所在位置）到点 $n + 1$（Boss 所在位置）的直线线段。

该关卡中布置了 $k$ 个陷阱。每个陷阱由三个整数 $l_i$、$r_i$ 和 $d_i$ 描述：$l_i$ 是陷阱的位置，$d_i$ 是该陷阱的危险等级；当一名敏捷值小于 $d_i$ 的士兵踩上该陷阱（即移动至点 $l_i$）时，他会立即死亡。幸运的是，你可以解除陷阱：若你移动至点 $r_i$，则该陷阱即被解除，此后不再对你的士兵构成任何威胁。注意：陷阱仅影响你的士兵，对你本人无影响。

你必须在 $t$ 秒内完成该关卡——即把若干名士兵从起点成功带至 Boss 所在位置。关卡开始前，你需要决定哪些士兵随你同行、哪些士兵留守。之后，你必须将所有选定的士兵全部带至 Boss 所在点 $n + 1$。为此，你可以执行以下操作：

• 若你当前位于位置 $x$，你可以移动至 $x + 1$ 或 $x - 1$，每次移动耗时 1 秒；
• 若你当前位于位置 $x$，且你的队伍也位于位置 $x$，则你可以带领整个队伍一起移动至 $x + 1$ 或 $x - 1$，耗时 1 秒；但该操作不可使任何士兵陷入危险（即：队伍即将移入的位置若存在尚未解除的陷阱 $i$，且其危险等级 $d_i$ 大于队伍中某名士兵的敏捷值 $a_j$，则该操作禁止执行）；
• 若你当前位于位置 $x$，且存在某个陷阱 $i$ 满足 $r_i = x$，则你可以立即解除该陷阱（不消耗时间）。

注意：每次操作后，你和你的队伍所处的位置坐标均为整数。

你需要选择尽可能多的士兵，使得他们全部能从点 $0$ 被安全带至点 $n + 1$（Boss 所在处），且总耗时不超过 $t$ 秒。

The first line contains four integers $m$, $n$, $k$ and $t$ ($1 \le m, n, k, t \le 2 \cdot 10^5$, $n \lt t$) — the number of soldiers, the number of integer points between the squad and the boss, the number of traps and the maximum number of seconds you may spend to bring the squad to the boss, respectively.

The second line contains $m$ integers $a_1$, $a_2$, ..., $a_m$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the agility of the $i$-th soldier.

Then $k$ lines follow, containing the descriptions of traps. Each line contains three numbers $l_i$, $r_i$ and $d_i$ ($1 \le l_i \le r_i \le n$, $1 \le d_i \le 2 \cdot 10^5$) — the location of the trap, the location where the trap can be disarmed, and its danger level, respectively.

第一行包含四个整数 $m$、$n$、$k$ 和 $t$（$1 \le m, n, k, t \le 2 \cdot 10^5$，且 $n \lt t$），分别表示士兵人数、小队与 Boss 之间的整数坐标点数量、陷阱数量以及将小队带至 Boss 处所允许的最长时间（单位：秒）。

第二行包含 $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$），分别表示该陷阱的位置、可解除该陷阱的位置，以及其危险等级。

Print one integer — the maximum number of soldiers you may choose so that you may bring them all to the boss in no more than $t$ seconds.

输出一个整数——在不超过 $t$ 秒的时间内，你能带到 Boss 处的士兵的最大数量。

In the first example you may take soldiers with agility $3$, $4$ and $5$ with you. The course of action is as follows:

• go to $2$ without your squad;
• disarm the trap $2$;
• go to $3$ without your squad;
• disartm the trap $3$;
• go to $0$ without your squad;
• go to $7$ with your squad.

The whole plan can be executed in $13$ seconds.

在第一个例子中，你可以带上敏捷值为 $3$、$4$ 和 $5$ 的士兵。具体行动步骤如下：

• 不带小队前往位置 $2$；
• 解除陷阱 $2$；
• 不带小队前往位置 $3$；
• 解除陷阱 $3$；
• 不带小队前往位置 $0$；
• 带上小队前往位置 $7$。

整个计划可在 $13$ 秒内完成。