2071 - お料理上手なんです、Kamba君

問題

お料理が上手なKamba君は、料理対決をしています。この勝負では、制限時間 $M$ 分以内に複数の料理を作り、「美味しさ」を競います。この「美味しさ」は数値で表されるものとします。
Kamba君は $N$ 種類の料理をマスターしています。料理 $i$ を作るには $T_i$ 分かかり、その料理の美味しさは $S_i$ 点です。Kamba君は制限時間内で、いくつかの料理を選んで作ることができます。ただし、勝負のルール上、同じ料理を複数回作ることはできません。
このとき、Kamba君が作ることができる料理の「美味しさ」の合計の最大値を求めてください。

入力

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

$M$ $N$
$T_1$ $S_1$
$T_2$ $S_2$
$:$
$:$
$T_N$ $S_N$

1行目に制限時間 $M$ と料理の種類数 $N$ が与えられる。
2行目以降に料理 $i$ を作るのにかかる時間 $T_i$ と美味しさ $S_i$ が与えられる。$(1 \leq i \leq N)$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq M \leq 10^4$
• $1 \leq N \leq 10^4$
• $1 \leq T_i \leq M$
• $1 \leq S_i \leq 7.4 \times 10^{8}$
• 入力はすべて整数である。

入出力例

入力例

10 5
4 1000
3 800
5 1500
2 740
6 1200

出力例

3040

料理 $2$, 料理 $3$, 料理 $4$ を作る時、スコアが最大になります。