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

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

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

【样例1解释】
在第 1, 2 天跑步打卡， 第 3 天不跑步打卡， 最终会获得 (−1) + (−1) + 4 = 2 的能量值。
【数据范围】
记 li = xi − yi + 1 ，ri = xi；
对于所有测试数据，保证：1 ≤ t ≤ 10，1 ≤ k ≤ n ≤ 109，1 ≤ m ≤ 105，1 ≤ li ≤ ri ≤ n， 1 ≤ d, vi ≤ 109。

特殊性质 A：k ≤ 102；
特殊性质 B：A1 ≤ i < m ，ri < li+1；
特殊性质 C：A1 ≤ i < j ≤ m ，li < lj ，ri < rj 。

NOIP