/ 
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)
- 入力は全て整数
小課題・得点
この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
それぞれの小課題は上の制約に加えて、それぞれ次の制約を満たします。
- (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 日目までの 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 の制約を満たします。