天天爱打卡
时间限制：1秒 内存限制：256M
【题目描述】
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。
开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 \(n\) 天，编号为从 \(1\) 到 \(n\)。
对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 \(d\)。初始时，他的能量值是 \(0\)，并且试运行期间他的能量值可以是负数。而且大 Y 不会连续跑步打卡超过 \(k\) 天；即不能存在 \(1≤x≤n−k\)，使得他在第 \(x\) 到第 \(x+k\) 天均进行了跑步打卡。
小 T 同学在软件中设计了 \(m\) 个挑战，第 \((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】
Input
1 1
3 2 2 1
2 2 4
3 2 3
Output
2
【样例1解释】
在第 \(1,2\) 天跑步打卡，第 \(3\) 天不跑步打卡，最终会获得 \((−1)+(−1)+4=2\) 的能量值。
【输入输出样例2】
该组样例满足测试点 3 的条件。
【输入输出样例3】
该组样例满足测试点 5 的条件。
【输入输出样例4】
该组样例满足测试点 15 的条件。
【输入输出样例5】
该组样例满足测试点 17 的条件。
【输入输出样例6】
该组样例满足测试点 17 的条件。
【数据范围】
记 \(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\)。
特殊性质 A：\(k≤10^2\)；
特殊性质 B：\(∀1≤i<m，r_i<l_i+1\)；
特殊性质 C：\(∀1≤i<j≤m，l_i<l_j，r_i<r_j\)。
