题目描述

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

Format

输入格式

输入的第一行包含两个整数 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 的能量值。

样例解释#2

该组样例满足测试点 3 的条件。

样例解释#3

该组样例满足测试点 5 的条件。

样例解释#4

该组样例满足测试点 15 的条件。

样例解释#5

该组样例满足测试点 17 的条件。

样例解释#6

该组样例满足测试点 19 的条件。

数据范围

记 $l_i=x_i-y_i+1,r_i=x_i$ 对于所有测试数据，保证:$1\leq t \leq 10$,$1\leq k \leq n \leq 10^9$, $1\leq m \leq 10^5$,$1\leq l_i \leq r_i \leq n$,$1\leq d,v_i \leq 10^9$,

特殊性质 A: $k<=10^2$

特殊性质 B: ${\forall} 1 \leq i <m ,r_i<l_{i+1}$

特殊性质 C: ${\forall} 1 \leq i < j <m,l_i<l_{j},r_i < r_j$