#10000034. 【NOIP 2023】天天爱打卡（run）

提交源程序文件名

【题目描述】

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

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

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

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

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

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

【输入格式】

从文件 中读入数据。

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

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

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

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

• 接下来 行，每行包含三个正整数 ，表示一次挑战。

【输出格式】

输出到文件 中。

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

【样例 输入】

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

【样例 输出】

2

【样例 解释】

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【样例 】

见选手目录下的 与 。

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

【数据范围】

记 ，；

对于所有测试数据，保证：，，，，。

特殊性质 ：；

特殊性质 ：，；

特殊性质 ：，，。