你正在玩一款电脑游戏,你领导着一支由 $$$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$$$,你可以解除这个陷阱。此操作立即完成(不消耗时间)。
请注意,每次动作后,你的坐标和你的小队的坐标都应该是整数。
你必须选择最大数量的士兵,以便在不超过 $$$t$$$ 秒的时间内将他们全部从 $$$0$$$ 点带到 $$$n + 1$$$ 点(boss 等待的地方)。
输入
第一行包含四个整数 $$$m$$$、$$$n$$$、$$$k$$$ 和 $$$t$$$ ($$$1 \le m, n, k, t \le 2 \cdot 10^5$$$, $$$n < 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$$$) — 分别是陷阱的位置、可以解除陷阱的位置及其危险级别。
输出
打印一个整数——你可以选择的最大士兵数量,这样你就可以在不超过 $$$t$$$ 秒的时间内将他们全部带到老板面前。
示例
输入 #1
5 6 4 14 1 2 3 4 5 1 5 2 1 2 5 2 3 5 3 5 3
输出 #1
3
注意
在第一个例子中,你可以带着敏捷的士兵 $$$3$$$、$$$4$$$ 和 $$$5$$$ 随身携带。行动过程如下:
- 在没有你的小队的情况下前往$$$2$$$;
- 解除陷阱$$$2$$$;
- 在没有你的小队的情况下前往$$$3$$$;
- 解除陷阱$$$3$$$;
- 在没有你的小队的情况下前往$$$0$$$;
- 和你的小队一起前往$$$7$$$。
整个计划可以在$$$13$$$秒内执行。