题目描述

小 $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$ 天结束后，他的能量值最高可以达到多少？

---

输入格式

从文件 run.in 中读入数据。

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

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

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

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

---

输出格式

输出到文件 run.out 中。

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

---

样例 1

输入

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

输出

2

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

---

样例 2

见附加文件中的 run2.in 和 run2.ans。

该组样例满足测试点 $3$ 的限制。

---

样例 3

见附加文件中的 run3.in 和 run3.ans。

该组样例满足测试点 $5$ 的限制。

---

样例 4

见附加文件中的 run4.in 和 run4.ans。

该组样例满足测试点 $15$ 的限制。

---

样例 5

见附加文件中的 run5.in 和 run5.ans。

该组样例满足测试点 $17$ 的限制。

---

样例 6

见附加文件中的 run6.in 和 run6.ans。

该组样例满足测试点 $19$ 的限制。

---

数据范围与提示

记 $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$。

测试点编号	$n \le$	$m \le$	特殊性质
1, 2	$18$	$10^2$	无
3, 4	$10^2$
5~7	$10^3$
8, 9	$10^5$
10, 11		$10^3$
12~14
15, 16	$10^9$		A
17, 18			B
19~21			C
22~25			无

• 特殊性质 A：$k \le 10^2$；
• 特殊性质 B：$\forall 1 \le i < m$，$r_i < l_{i+1}$；
• 特殊性质 C：$\forall 1 \le i < j \le m$，$l_i < l_j$，$r_i < r_j$。