037 - Don't Leave the Spice(★5)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 5 点
問題文
香辛料を使う料理が N 種類あり、1 から N までの番号が付いています。
料理 i (1 \le i \le N) の価値は V_i で、作るときに香辛料を消費します。消費する香辛料の量は L_i [\mathrm{mg}] 以上 R_i [\mathrm{mg}] 以下の範囲で調節できます。
以下のことが実現可能かどうか判定し、可能な場合は作る料理の価値の合計としてあり得る最大の値を出力してください。
N 種類の料理から何種類かを選んで 1 つずつ 作ることで、香辛料を ちょうど W [\mathrm{mg}] 消費する。
ただし、上で述べたもの以外の手段で香辛料を消費することはできない。
制約
- 1 \leq W \leq 10^4
- 1 \leq N \leq 500
- 1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
W N L_1 R_1 V_1 L_2 R_2 V_2 \vdots L_N R_N V_N
出力
作る料理の価値の合計としてあり得る最大値を出力してください。
香辛料をちょうど W [\mathrm{mg}] 消費することが不可能な場合は、 -1 を出力してください。
入力例 1
100 4 30 40 120 30 40 30 30 40 1500 30 40 40
出力例 1
1660
料理 1 、料理 3 、料理 4 を、それぞれ香辛料を \frac{100}{3} [\mathrm{mg}] ずつ消費して作ると、価値の合計は 120+1500+40=1660 になります。
入力例 2
100 4 13 15 31415 12 13 92653 29 33 58979 95 98 32384
出力例 2
-1
香辛料をちょうど 100 [\mathrm{mg}] 消費することは不可能です。
入力例 3
5000 5 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000 1000 1000 1000000000
出力例 3
5000000000
入力例 4
10000 20 4539 6002 485976 1819 5162 457795 1854 2246 487643 1023 4733 393530 1052 6274 289577 1874 2436 167747 1457 4248 452660 2103 4189 174955 3057 5061 319316 4898 4953 394627 1313 2880 154687 1274 1364 259598 3866 5844 233027 1163 5036 386223 1234 4630 155972 2845 4978 442858 3168 5368 171601 3708 4407 394899 3924 4122 428313 2112 4169 441976
出力例 4
2727026