← 返回题目列表

AtCoder · typical90_ak

037. 不要离开香料(★5)

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

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