#216355. [蓝桥杯 2026 省 Python C 组] 智能产线排程优化

某智能制造工厂拥有两条完全相同且可以并行工作的自动化生产线，分别记为 A 和 B。现在，工厂同时接到了 份生产订单。

对于第 份订单（），给定以下三个参数：

• 加工时间 ：该订单在任意一条生产线上加工所需的时间；
• 交付期限 ：该订单必须在第 小时之前（含第 小时）完成；
• 订单收益 ：若该订单按时完成，工厂可以获得的收益。

两条生产线都从第 0 小时开始运行，并且彼此独立。对于任意一条生产线：

• 同一时刻最多只能加工一份订单；
• 每份订单一旦开始加工，就必须连续完成，不能中断；
• 相邻订单之间没有切换时间。

工厂可以从这 份订单中选择任意若干份进行生产。对于每一份被选择的订单，需要决定：

• 将其分配给生产线 A 或生产线 B；
• 它在对应生产线上的加工顺序。

要求所有被选择的订单都必须在各自的交付期限内完成。对此，请你计算：工厂最多能够获得多少收益。

第一行包含一个正整数 ，表示订单数量。

接下来 行，每行包含三个正整数 ，分别表示第 份订单的加工时间、交付期限和收益。

输出一行，包含一个整数，表示能够获得的最大总收益。

样例输入 1

4
3 4 10
3 5 12
2 3 6
4 7 15

样例输出 1

43

样例输入 2

5
3 4 10
2 3 7
4 6 20
3 7 12
5 8 18

样例输出 2

60

【样例说明 1】

四份订单的信息如下：

一种最优安排如下：

• 生产线 A：先加工订单 ，再加工订单 ；
• 生产线 B：先加工订单 ，再加工订单 。

具体完工情况为：

• 生产线 A：

  • 订单 在第 小时加工，完工时刻为 ，满足 ；
  • 订单 在第 小时加工，完工时刻为 ，满足 。

• 生产线 B：

  • 订单 在第 小时加工，完工时刻为 ，满足 ；
  • 订单 在第 小时加工，完工时刻为 ，满足 。

四份订单均可按时完成，总收益为：

【样例说明 2】

五份订单的总加工时间为：

在最晚交付期限为 的情况下，两条生产线在时间区间 内总共最多只能提供 个单位的加工时间，因此不可能将全部订单都安排并按时完成。

一种最优方案是放弃订单 ，选择订单 。安排如下：

• 生产线 A：先加工订单 ，再加工订单 ；
• 生产线 B：先加工订单 ，再加工订单 。

对应的完工时刻分别为：

• 订单 ：完工时刻为 ，满足 ；
• 订单 ：完工时刻为 ，满足 ；
• 订单 ：完工时刻为 ，满足 ；
• 订单 ：完工时刻为 ，满足 。

这四份订单均能按时完成，因此总收益为：

可以证明，不存在收益大于 的可行方案，因此答案为 。

【评测用例规模与约定】

• 对于 的评测用例，满足 ；
• 对于 的评测用例，满足 ，且 ；
• 对于所有的评测用例，，，，。