D. 天天爱打卡
time limit per test
2.5 s
memory limit per test
512 megabytes
input
run.in
output
run.out

小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。

开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $$$n$$$ 天，编号为从 $$$1$$$ 到 $$$n$$$。

对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $$$d$$$。初始时，他的能量值是 $$$0$$$，并且试运行期间他的能量值可以是负数。

而且大 Y 不会连续跑步打卡超过 $$$k$$$ 天；即不能存在 $$$1\le x\le n-k$$$，使得他在第 $$$x$$$ 到第 $$$x+k$$$ 天均进行了跑步打卡。

小 T 同学在软件中设计了 $$$m$$$ 个挑战，第 $$$i$$$（$$$1\le i \le m$$$）个挑战可以用三个正整数 $$$(x_i,y_i,v_i)$$$ 描述，表示如果在第 $$$x_i$$$ 天时，用户已经连续跑步打卡至少 $$$y_i$$$ 天（即第 $$$x_i-y_i+1$$$ 到第 $$$x_i$$$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $$$v_i$$$。

现在大 Y 想知道，在软件试运行的 $$$n$$$ 天结束后，他的能量值最高可以达到多少？

Input

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 $$$c$$$ 和 $$$t$$$，分别表示测试点编号和测试数据组数。对于样例，$$$c$$$ 表示该样例与测试点 $$$c$$$ 拥有相同的限制条件。

接下来，对于每组测试数据：

  • 输入的第一行包含四个正整数 $$$n,m,k,d$$$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
  • 接下来 $$$m$$$ 行，每行包含三个正整数 $$$x_i,y_i,v_i$$$，表示一次挑战。
Output

输出一行一个整数表示对应的答案。

Example
Input
1 1
3 2 2 1
2 2 4
3 2 3
Output
2
Note

【样例解释 #1】

在第 $$$1,2$$$ 天跑步打卡，第 $$$3$$$ 天不跑步打卡，最终会获得 $$$(-1)+(-1)+4=2$$$ 的能量值。

【数据范围】

记 $$$l_i=x_i-y_i+1$$$，$$$r_i=x_i$$$；

对于所有测试数据，保证：$$$1\le t\le 10$$$，$$$1\le k\le n\le 10^9$$$，$$$1\le m\le 10^5$$$，$$$1\le l_i\le r_i\le n$$$，$$$1\le d,v_i\le 10^9$$$。