3924. T4-[NOIP2023] 天天爱打卡(run)
时间限制：2000 MS 内存限制：512 MB
题目描述
## 题目描述 小 $ T $ 同学非常热衷于跑步。 为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。 开发完成后，小 $ T $ 同学计划进行试运行，他找了大 $ Y $ 同学来帮忙。 试运行共 $ n $ 天，编号为从 $ 1 $ 到 $ n $ 。 对大 $ Y $ 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $ d $ 。 初始时，他的能量值是 $ 0 $ ，并且试运行期间他的**能量值可以是负数**。 而且大 $ Y $ 不会**连续**跑步打卡**超过** $ k $ 天；即不能存在 $ 1\lex\len-k $ ，使得他在第 $ x $ 到第 $ x+k $ 天均进行了跑步打卡。 小 $ T $ 同学在软件中设计了 $ m $ 个挑战，第 $ i（1\lei\lem） $ 个挑战可以用三个正整数 $ (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 $ ，表示一次挑战。 ## 输出格式 输出一行一个整数表示对应的答案。 ## 数据范围 记 $ l_i=x_i-y_i+1，r_i=x_i $ ； 对于所有测试数据，保证： $ 1\let\le10，1\lek\len\le10^9，1\lem\le10^5，1\lel_i\ler_i\len，1\led,v_i\le10^9 $ 。  特殊性质 $ A $ ： $ k\le10^2 $ ； 特殊性质 $ B $ ： $ \forall1\lei<m，r_i<l_{i+1} $ ； 特殊性质 $ C $ ： $ \forall1\lei<j\lem，l_i<l_j，r_i<r_j $ 。 ```in4 1 1 3 2 2 1 2 2 4 3 2 3 ``` ```out4 2 ``` ## 说明 在第 1,2 天跑步打卡，第 3 天不跑步打卡，最终会获得 (-1)+(-1)+4=2 的能量值。