外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

E - Desire for Cat Food

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 300 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんは、所持金 MM 円を握りしめて猫缶専門店「にゃいすふ〜ど」へやってきました。
にゃいすふ〜どでは NN 個の猫缶が売られており、ii 番目の猫缶は価格が KiK_i 円で、大きさが ViV_i です。

わりとねこくんは、購入する猫缶の価格の合計が所持金 MM 円以下となるように、いくつか猫缶を選んで買おうとしています。
ただし、各猫缶は 11 つずつしか売られていないため、同じ猫缶を複数個買うことはできません(11 個も買わないことも可能です)。

わりとねこくんが買うことのできる猫缶の大きさの合計の最大値を求めてください。

制約

  • 1≤M≤1041 \le M \le 10^4
  • 1≤N≤1001 \le N \le 100
  • 1≤Ki≤M1 \le K_i \le M
  • 1≤Vi≤1091 \le V_i \le 10^9
  • 入力はすべて整数

入力

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

MNM \quad N K1V1K_1 \quad V_1 K2V2K_2 \quad V_2 ⋮\vdots KNVNK_N \quad V_N

出力

購入できる猫缶の大きさの合計の最大値を 11 行に出力してください。

サンプル 1

入力

10 4
6 13
5 10
5 10
4 6

出力

20

たとえば、2,32, 3 個目の猫缶を 1010 円で買うことができ、このときの猫缶の大きさの総和は 2020 です。 これ以上大きさの総和を大きくすることはできないため、2020 を出力します。

サンプル 2

入力

7 3
4 9
5 10
6 11

出力

11

サンプル 3

入力

4 4
1 1000000000
1 1000000000
1 1000000000
1 1000000000

出力

4000000000

参加受付は終了しました。