もんだいー
DP学園では明日テストが行われます。
しかしその学園の生徒である、でぃっぴ君は全く勉強をしておらずこのままだと０点を取ってしまいます。
でぃっぴ君はとても困っていました。
その日の学校の帰り道、でぃっぴ君は本屋によってみたところ素晴らしい本を見つけました。
その内容は「ｍ分勉強すれば、確実にp点あがる」というものです。
でぃっぴ君は迷わずその本をｎ種類買っていきました。
でぃっぴ君はこれで、明日のテストは安心だと思いました。
しかし、でぃっぴ君の頭には「t分勉強すると、勉強したことををすべて忘れてしまう」という問題があったのです！
ｔ分以内の勉強時間でどの本を選べば効率よく点がとれるか分からず、でぃっぴ君はまた困ってしまいました。
その事情を知ったあなたは、でぃっぴ君のためにプログラムを作成することにしました。
勉強時間がｔ分を超えない範囲で取れる、最大の合計点数を出力するプログラムを作成してください。
ただし、同じ本は一度しか使えません。
[まとめ]
「ｍ分勉強すれば、確実にp点あがる」というn種類の本がある。
その情報から「勉強時間がｔ分を超えない範囲で取れる、最大の合計点数を出力するプログラム」を作成する。
[注意]
・同じ本は一度しか使えない。
・最初の状態のでぃっぴ君が取れる点数は0点。そこから本を読んでいくことで取れる点数が加算されていく。
・最大の合計点数が0の場合は0を出力。
入力
t n m1 p1 m2 p2 . . . mn pn
t:でぃっぴ君が勉強できる時間（分） n:本の数 mi:i番目の本を読むのにかかる時間（分） pi:i番目の本を読むことで取れる点数
出力
勉強時間がｔ分を超えない範囲で取れる、最大の合計点数
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ t, n, m, p ≦ 1000
入出力例
入力例1
50 5 10 60 20 100 30 120 45 210 4 10
出力例1
220
入力例2
100 10 52 67 35 53 22 2 1 84 18 156 70 25 65 2 49 72 34 29 66 197
出力例2
437