题目描述

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

对于第 $i$ 份订单（$1 \le i \le N$），给定以下三个参数：

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

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

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

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

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

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

输入格式

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

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

输出格式

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

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

43

解释 #1

四份订单的信息如下：

一种最优安排如下：

• 生产线 A：先加工订单 $3$，再加工订单 $2$；
• 生产线 B：先加工订单 $1$，再加工订单 $4$。

具体完工情况为：

• 生产线 A：

  • 订单 $3$ 在第 $0 \sim 2$ 小时加工，完工时刻为 $2$，满足 $2 \le d_3 = 3$；
  • 订单 $2$ 在第 $2 \sim 5$ 小时加工，完工时刻为 $5$，满足 $5 \le d_2 = 5$。

• 生产线 B：

  • 订单 $1$ 在第 $0 \sim 3$ 小时加工，完工时刻为 $3$，满足 $3 \le d_1 = 4$；
  • 订单 $4$ 在第 $3 \sim 7$ 小时加工，完工时刻为 $7$，满足 $7 \le d_4 = 7$。

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

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

60

解释 #2

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

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

一种最优方案是放弃订单 $2$，选择订单 $\{1, 3, 4, 5\}$。安排如下：

• 生产线 A：先加工订单 $3$，再加工订单 $4$；
• 生产线 B：先加工订单 $1$，再加工订单 $5$。

对应的完工时刻分别为：

• 订单 $3$：完工时刻为 $4$，满足 $4 \le d_3 = 6$；
• 订单 $4$：完工时刻为 $7$，满足 $7 \le d_4 = 7$；
• 订单 $1$：完工时刻为 $3$，满足 $3 \le d_1 = 4$；
• 订单 $5$：完工时刻为 $8$，满足 $8 \le d_5 = 8$。

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

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

数据范围

• 对于 $30\%$ 的评测用例，满足 $N \le 15$；
• 对于 $60\%$ 的评测用例，满足 $N \le 50$，且 $d_i \le 300$；
• 对于所有的评测用例，$1 \le N \le 200$，$1 \le p_i \le 50$，$p_i \le d_i \le 1000$，$1 \le r_i \le 10000$。