← 返回题目列表

AtCoder · typical90_k

011. 肉汁工作(★6)

中文机器翻译题面 查看原题

配点: 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)
  • 所有输入均为整数

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。

  1. (2 点): N\leq8
  2. (2 点): N\leq20
  3. (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 约束。