問題文

香辛料を使う料理が 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)
• 入力はすべて整数

入力例 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