时空限制

1S/512M

题目描述

Nailong 想要玩游戏，但他需要考虑电脑的性能。具体地，他电脑的性能值为 $x$。

为了防止电脑蓝屏，Nailong 预知了接下来的 $n$ 秒内会出现的 $m$ 个进程。其中第 $i$ 个进程会在第 $[l_i, r_i]$ 秒内运行，并给电脑带来 $a_i$ 点负担。

如果在接下来的 $n$ 秒内，累计有至少 $k$ 秒满足“电脑的总负担严格大于电脑性能 $x$”，那么电脑就会蓝屏。

Nailong 打算在接下来的 $n$ 秒内玩一个游戏，该游戏会全程给电脑带来一个恒定的负担。他想知道，在保证电脑不蓝屏的前提下，他能玩的游戏的最大负担是多少。

特别地，如果 Nailong 不玩任何游戏（即游戏负担为 $0$）时电脑也会蓝屏，请输出 -1。

格式

输入格式

第一行包含四个整数 $n, m, k, x$，含义详见题目描述。

接下来的 $m$ 行，每行包含三个整数 $l_i, r_i, a_i$，分别表示第 $i$ 个进程的开始时间、结束时间以及产生的负担。

输出格式

输出一个整数，表示 Nailong 能玩的游戏的最大负担。如果无法运行任何游戏，输出 -1。

样例

样例输入 #1

4 3 2 9
1 4 2
1 3 4
3 4 1

样例输出 #1

3

样例输入 #2

4 3 2 3
1 4 2
1 3 4
3 4 1

样例输出 #2

-1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le k \le n \le 10^5, 0 \le m \le 10^5, 1 \le x \le 10^9, 1 \le l_i \le r_i \le n, 1 \le a_i \le 10^4$。