#2043. 「NOIP 2023」天天爱打卡

内存限制:512 MiB 时间限制:2000 ms 输入文件:run.in 输出文件:run.out
题目类型:传统 评测方式:文本比较
上传者: HHOJ

题目描述

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

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

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

而且大 Y 不会连续跑步打卡超过 天;即不能存在 ,使得他在第 到第 天均进行了跑步打卡。

小 T 同学在软件中设计了 个挑战,第 )个挑战可以用三个正整数 描述,表示如果在第 天时,用户已经连续跑步打卡至少 天(即第 到第 天均完成了跑步打卡),那么小 T 同学就会请用户吃饭,从而使用户的能量值提高

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

输入格式

从文件 run.in 中读入数据。

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

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

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

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

输出格式

输出到文件 run.out 中。

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

样例

样例 1 输入

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

样例 1 输出

2

样例 1 解释

在第 天跑步打卡,第 天不跑步打卡,最终会获得 的能量值。

样例 2

见附加文件中的 run/run2.inrun/run2.ans

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

样例 3

见附加文件中的 run/run3.inrun/run3.ans

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

样例 4

见附加文件中的 run/run4.inrun/run4.ans

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

样例 5

见附加文件中的 run/run5.inrun/run5.ans

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

样例 6

见附加文件中的 run/run6.inrun/run6.ans

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

数据范围与提示

​;

对于所有测试数据,保证:

测试点编号 特殊性质
A
B
C

特殊性质 A:

特殊性质 B:

特殊性质 C: