011 - Gravy Jobs(★6) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 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 日目までの 3 日をかけて 1 番目の仕事を完了することで 69853 円を得ることができます。

69853 円より多く報酬を得ることはできないため、答えは 69853 円です。


入力例 2

3
7 3 200000
3 2 100000
5 3 150000

出力例 2

350000

2 日目から 4 日目までの 3 日をかけて 3 番目の仕事を、5 日目から 7 日目までの 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 の制約を満たします。


Source Name

「競プロ典型90問」11日目