天天爱打卡

题目描述:

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

输入格式:

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

输入的第一行包含两个整数 \(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\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\)|\(10 ^ 2\)|无|
|\(5 \sim 7\)|\(10 ^ 3\)|\(10 ^ 3\)|无|
|\(8, 9\)|\(10 ^ 3\)|\(10 ^ 5\)|无|
|\(10, 11\)|\(10 ^ 5\)|\(10 ^ 3\)|无|
|\(12 \sim 14\)|\(10 ^ 5\)|\(10 ^ 5\)|无|
|\(15, 16\)|\(10 ^ 9\)|\(10 ^ 5\)|A|
|\(17, 18\)|\(10 ^ 9\)|\(10 ^ 5\)|B|
|\(19 \sim 21\)|\(10 ^ 9\)|\(10 ^ 5\)|C|
|\(22 \sim 25\)|\(10 ^ 9\)|\(10 ^ 5\)|无|

特殊性质 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\)。

时间限制: 2000ms
空间限制: 512MB

---

来源: NOIP2023提高T4