#214459. [JOISC 2019] 两道料理 / Two Dishes

本题测试数据较大，可能需要 1-1.5 分钟的时间加载测试数据。

Bitaro 正在参加一场烹饪比赛。在本比赛中，参赛者需要制作两道菜：IOI 盖饭和 JOI 咖喱。

IOI 盖饭的烹饪过程包含 个步骤。第 步（）恰好需要 分钟。初始时，他只能执行第一步。要执行第 步（），他必须先完成第 步。

JOI 咖喱的烹饪过程包含 个步骤。第 步（）恰好需要 分钟。初始时，他只能执行第一步。要执行第 步（），他必须先完成第 步。

步骤需要集中精力，因此一旦他开始执行某个步骤，就必须完成该步骤后才能执行其他步骤。在步骤之间，他可以从一道菜切换到另一道菜。比赛开始后，他必须完成两道菜后才能休息。

顺便说明，在本比赛中，参赛者将获得如下艺术评分：

• 若他在比赛开始后 分钟内完成 IOI 盖饭的第 步（），则获得 分。此处， 的值可能为负数。
• 若他在比赛开始后 分钟内完成 JOI 咖喱的第 步（），则获得 分。此处， 的值可能为负数。

Bitaro 希望最大化他的总艺术评分。

编写一个程序，在给定烹饪步骤数量、各步骤所需时间以及艺术评分信息后，计算 Bitaro 能获得的最大总艺术评分。

从标准输入读取以下数据。输入中的所有数值均为整数。

向标准输出写入一行。输出应包含 Bitaro 能获得的最大总艺术评分。

样例输入 1

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

样例输出 1

6

样例输入 2

5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8

样例输出 2

63

样例输入 3

9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19

样例输出 3

99

样例 1 解释

本样例输入满足子任务 2 的约束条件。

在本样例输入中，Bitaro 可按如下方式执行烹饪步骤，例如：

1. 他执行 JOI 咖喱的第 1 步。他在比赛开始后 3 分钟完成。由于该时间在 6 分钟内，他获得 1 分。
2. 他执行 IOI 盖饭的第 1 步。他在比赛开始后 5 分钟完成。由于该时间不在 1 分钟内，他未获得艺术评分。
3. 他执行 IOI 盖饭的第 2 步。他在比赛开始后 8 分钟完成。由于该时间在 8 分钟内，他获得 1 分。
4. 他执行 JOI 咖喱的第 2 步。他在比赛开始后 10 分钟完成。由于该时间在 11 分钟内，他获得 1 分。
5. 他执行 IOI 盖饭的第 3 步。他在比赛开始后 12 分钟完成。由于该时间在 13 分钟内，他获得 1 分。
6. 他执行 IOI 盖饭的第 4 步。他在比赛开始后 13 分钟完成。由于该时间在 13 分钟内，他获得 1 分。
7. 他执行 JOI 咖喱的第 3 步。他在比赛开始后 15 分钟完成。由于该时间在 15 分钟内，他获得 1 分。

此处，总艺术评分为 6 分。他无法获得超过 6 分，因此输出 6。

数据范围

• 。
• 。
• （）。
• （）。
• （）。
• （）。
• （）。
• （）。

子任务

1. （5 分），，。
2. （3 分），，（），（）。
3. （7 分），，（），（）。
4. （39 分），，（），（）。
5. （11 分），，（），（）。
6. （9 分）（），（）。
7. （17 分），。
8. （9 分）无额外约束。

翻译由 Qwen3-235B 完成