#NOIP2023D. 天天爱打卡

天天爱打卡

题目描述

小 T 同学非常热衷于跑步。为了让跑步更加有趣,他决定制作一款叫做《天天爱打卡》的软件,使得用户每天都可以进行跑步打卡。

开发完成后,小 T 同学计划进行试运行,他找了大 Y 同学来帮忙。试运行共 nn 天,编号为从 11nn

对大 Y 同学来说,如果某天他选择跑步打卡,那么他的能量值会减少 dd。初始时,他的能量值是 00,并且试运行期间他的能量值可以是负数

而且大 Y 不会连续跑步打卡超过 kk 天;即不能存在 1xnk1\le x\le n-k,使得他在第 xx 到第 x+kx+k 天均进行了跑步打卡。

小 T 同学在软件中设计了 mm 个挑战,第 ii1im1\le i \le m)个挑战可以用三个正整数 (xi,yi,vi)(x_i,y_i,v_i) 描述,表示如果在第 xix_i 天时,用户已经连续跑步打卡至少 yiy_i 天(即第 xiyi+1x_i-y_i+1 到第 xix_i 天均完成了跑步打卡),那么小 T 同学就会请用户吃饭,从而使用户的能量值提高 viv_i

现在大 Y 想知道,在软件试运行的 nn 天结束后,他的能量值最高可以达到多少?

输入格式

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

输入的第一行包含两个整数 cctt,分别表示测试点编号和测试数据组数。对于样例,cc 表示该样例与测试点 cc 拥有相同的限制条件。

接下来,对于每组测试数据:

  • 输入的第一行包含四个正整数 n,m,k,dn,m,k,d,分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
  • 接下来 mm 行,每行包含三个正整数 xi,yi,vix_i,y_i,v_i,表示一次挑战。

输出格式

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

1 1
3 2 2 1
2 2 4
3 2 3
2

提示

【样例解释 #1】

在第 1,21,2 天跑步打卡,第 33 天不跑步打卡,最终会获得 (1)+(1)+4=2(-1)+(-1)+4=2 的能量值。

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【样例解释 #5】

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

【样例解释 #6】

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

【数据范围】

li=xiyi+1l_i=x_i-y_i+1ri=xir_i=x_i​;

对于所有测试数据,保证:1t101\le t\le 101kn1091\le k\le n\le 10^91m1051\le m\le 10^51lirin1\le l_i\le r_i\le n1d,vi1091\le d,v_i\le 10^9

测试点编号 nn \le mm \le 特殊性质
1,21, 2 1818 10210 ^ 2
3,43, 4 10210 ^ 2
575 \sim 7 10310 ^ 3 10310 ^ 3
8,98, 9 10510 ^ 5
10,1110, 11 10510 ^ 5 10310 ^ 3
121412 \sim 14 10510 ^ 5
15,1615, 16 10910 ^ 9 A
17,1817, 18 B
192119 \sim 21 C
222522 \sim 25

特殊性质 A:k102k\le 10^2

特殊性质 B:1i<m\forall 1\le i<mri<li+1r_i<l_{i+1}

特殊性质 C:1i<jm\forall 1\le i<j\le mli<ljl_i<l_jri<rjr_i<r_j