001 - テスト勉強

もんだいー

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