配点: 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