7253 - 天天爱打卡(run)

小 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
3 2 2 1
2 2 4
3 2 3

输出

2

提示

【样例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

时间限制 2 秒
内存限制 512 MB
讨论 统计
上一题 下一题