コンテスト

競技プログラミング部 Antsでは 分間のコンテストが開催される予定です。問題は 問あり、 から まで番号が付けられています。

コンテスト開始から 分後に問題 に正解した場合、 点を得ることができます。

部員のmomoyuu君はコンテスト開始前に超能力により、コンテスト中に連続した 分を使うことで問題 に正解できることが分かりました。正確には、コンテスト開始 分後に問題 を解き始めた場合、 であれば問題 に正解し、 点を得ることができます。momoyuu君は頑固なので一つの問題を解き始めたらその問題に正解するまで他の問題を解き始めることはできません。問題に正解後次の問題を解き始めるまでの時間は考えないものとします。

全ての問題に正解する必要はなく、また問題を好きな順番で解くことができるとき、momoyuu君は最大で何点取ることができますか。一度正解した問題を再び解くことはできないものとします。

• 入力は全て整数

入力は以下の形式で標準入力で与えられる。

答えを出力せよ。

3 10
1 100 10
4 200 20
5 300 30

210

以下のような順番で解くことが最適です。

• コンテスト開始 秒後に問題 を解き始め、コンテスト開始 秒後に正解し、 点得る。
• コンテスト開始 秒後に問題 を解き始め、コンテスト開始 秒後に正解し、 点得る。
• コンテスト開始 秒後に問題 を解き始め、コンテスト開始 秒後に正解し、 点得る。

逆に、どのような解き方をしても 点より多くの得点を得ることはできないため、これが答えとなります。

10 1000
18 7151 183
8 5747 887
13 2522 657
10 6301 273
13 7572 236
94 3647 139
37 7069 347
65 9442 500
39 1205 210
82 9955 218