A Game with Traps

题意翻译

你有 $m$ 为士兵，每个士兵敏捷值为 $a_i(1 \leq a_i \leq 2\cdot10^5）$。 你要带领士兵从线段的 $0$ 点到 $n+1(1 \leq n \leq 2\cdot10^5）$ 点。 线段上有 $k(1 \leq k \leq 2\cdot10^5）$ 个陷阱，$l_i(1 \leq l_i \leq 2\cdot10^5）$ 代表第 $i$ 个陷阱的位置，$d_i(1 \leq d_i \leq 2\cdot10^5）$ 为危险等级（当士兵移动至 $l_i$ 且 $a_i<d_i$，就会被杀死，陷阱无法伤害你）。当士兵走到 $r_i(1 \leq r_i \leq 2\cdot10^5）$ 时，可以解除这个陷阱。 你要选择一些士兵，并在 $t(1 \leq t \leq 2\cdot10^5）$ 秒内带着**所有的**士兵走到 $n+1$ 点，你可以进行以下操作： - 若你的位置是 $x$，则可以耗费 $1$ 秒走到 $x-1$ 或 $x+1$。 - 若你和士兵的位置是 $x$，则可以耗费 $1$ 秒走到 $x-1$ 或 $x+1$，但不能让士兵处于危险之中。 - 若你的位置是 $x$，并且满足 $r_i=x$，你可以解除这个陷阱（不花费时间）。 在操作后，你和小队的坐标都应为整数。 你必须选择尽可能多的士兵，在 $t$ 秒内把它们从 $0$ 点带到 $n+1$ 点。

题目描述

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.

输入输出格式

输入格式

The first line contains four integers $ m $ , $ n $ , $ k $ and $ t $ ( $ 1 \le m, n, k, t \le 2 \cdot 10^5 $ , $ n < 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.

输出格式

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.

输入输出样例

输入样例 #1

5 6 4 14
1 2 3 4 5
1 5 2
1 2 5
2 3 5
3 5 3

输出样例 #1

3

说明

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.