题目描述

小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。 开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。 对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的能量值可以是负数 。 而且大 Y 不会连续跑步打卡超过$k$ 天；即不能存在 $1 ≤ x ≤ n − k$，使得他在第 $x$到第 $x + k$ 天均进行了跑步打卡。 小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1 ≤ i ≤ m$）个挑战可以用三个正整数 ($x_i$, $y_i$, $v_i$) 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第$x_i − y_i + 1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。 现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值最高可以达到多少？

输入

本题的测试点包含有多组测试数据。 输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。 接下来，对于每组测试数据： • 输入的第一行包含四个正整数 $n$, $m$, $k$, $d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。 • 接下来 $m$ 行，每行包含三个正整数 $x_i$, $y_i$, $v_i$，表示一次挑战。

输出

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

输入样例

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

输出样例

2

提示

【样例 1 解释】 在第 $1$, $2$ 天跑步打卡，第 $3$ 天不跑步打卡，最终会获得 $(−1) + (−1) + 4 = 2$ 的能量值。 【数据范围】 记 $l_i = x_i − y_i + 1$，$r_i = x_i$； 对于所有测试数据，保证：$1 ≤ t ≤ 10$，$1 ≤ k ≤ n ≤ 10^9$，$1 ≤ m ≤ 10^5$，$1 ≤ l_i ≤ r_i ≤ n$，$1 ≤ d, v_i ≤ 10^9$。

测试点编号	n ≤	m ≤	特殊性质
1, 2	18	102	无
3, 4	102
5 ∼ 7	103	103
8, 9		105
10, 11	10</sup>5</sup>	103
12 ∼ 14		105
15, 16	109		A
17, 18			B
19 ∼ 21			C
22 ∼ 25			无

特殊性质 A：$k ≤ 10^2$； 特殊性质 B：∀$1 ≤ i < m$，$r_i < l_i+1$； 特殊性质 C：∀$1 ≤ i < j ≤ m$，$l_i < l_j，r_i

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。