配点: 6 点
問題文
收到 ABC 君的工作委托 N 件。每项工作都有 1, 2, \cdots, N 。
仕事 i 截止日期为第 D_i 天结束,并且可以通过使用连续 C_i 天来完成。除此之外无法以其他方式完成工作。
更准确地说,为了在截止日期前完成工作 i ,必须从第C_i\leq k\leq D_i 的整数 在 k 关于 k-C_i+1 天开始到第 k 天结束,连续进行第 i 项工作。
仕事 i 若在截止日期前完成,可以获得 S_i 日元的报酬。1 天最多只能进行 1 种工作。
目前是 1 第一天开始。如果 ABC 君选择他能够顺利完成的工作并安排好日程,请求出他可以获得的报酬金额的最大值。
制約
- 1 \leq N \leq 5000
- 1 \leq D_i \leq 5000\ (1\leq i\leq N)
- 1 \leq C_i \leq 5000\ (1\leq i\leq N)
- 1 \leq S_i \leq 10^9\ (1\leq i\leq N)
- 所有输入均为整数
小课题·得点
这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。
- (2 点): N\leq8
- (2 点): N\leq20
- (2 分数):没有额外约束。
入力
输入是按以下格式从标准输入给出的。
N D_1 C_1 S_1 D_2 C_2 S_2 \vdots D_N C_N S_N
出力
请在一行上输出 ABC 君可以获得的报酬金额的最大值。
入力例 1
1 12 3 69853
出力例 1
69853
1 从第一天开始 3 到第 N 天为止 3 花费数天 1 完成第几项工作 69853 你可以获得日元。
69853 由于无法获得超过多少日元的报酬,因此答案为 69853 这是日元。
入力例 2
3 7 3 200000 3 2 100000 5 3 150000
出力例 2
350000
2 从第一天开始 4 到第 N 天为止 3 花费数天 3 第几项工作、5 从第一天开始 7 到第 N 天为止 3 花费数天 1 完成第几项工作 350000 你可以获得日元。
350000 由于无法获得超过多少日元的报酬,因此答案为 350000 这是日元。
入力例 3
8 376 640 602876667 4015 1868 533609371 3330 152 408704870 1874 798 30417810 2 1450 40706045 3344 1840 801881841 2853 1229 5235900 458 1277 997429858
出力例 3
1744196082
入力例 4
20 376 640 602876667 4015 868 533609371 3330 152 408704870 1874 798 30417810 2 450 40706045 3344 840 801881841 2853 229 5235900 458 277 997429858 1689 948 981897272 4774 393 997361572 4237 750 294800444 4663 293 277667068 2249 808 444906878 3341 137 845317003 3625 765 739689211 911 510 326127348 1343 193 235655766 842 323 406413067 1425 303 68833418 212 808 745744264
出力例 4
6583558066
此输入示例是一个小作业。 1 不满足约束,但小任务 2,3 约束。
入力例 5
30 376 140 602876667 4015 368 533609371 3330 152 408704870 1874 298 30417810 2 450 40706045 3344 340 801881841 2853 229 5235900 458 277 997429858 1689 448 981897272 4774 393 997361572 4237 250 294800444 4663 293 277667068 2249 308 444906878 3341 137 845317003 3625 265 739689211 911 10 326127348 1343 193 235655766 842 323 406413067 1425 303 68833418 212 308 745744264 3563 376 196296968 4186 323 275217640 332 361 337078801 4466 245 694789156 3763 250 432518459 2937 124 581390864 2255 227 642944345 2851 480 688009163 1957 295 5532462 3277 445 15791361
出力例 5
11420667389
此输入示例是一个小作业。 1,2 不满足约束,但小任务 3 约束。