Problem Statement

高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。 画面のスクリーンショットは $N$ 枚あり、高さは全て等しいのですが、幅が異なります。 また、表計算ソフトに貼りつけ可能なスクリーンショットには $2$ つの制約が存在します。

1. 表計算ソフトの幅は $W$ しかない。そのため、貼りつけるスクリーンショットの幅の合計値は $W$ 以下でなければならない。
2. 表計算ソフトは $K$ 枚より多くのスクリーンショットを貼りつけることが出来ない。よって、表計算ソフトに貼りつけ可能なスクリーンショットは $K$ 枚までである。

さらに、スクリーンショットには「重要度」が存在するため、高橋くんは $2$ つの制約を満たしながら、貼り付けるスクリーンショットが持つ重要度の合計値を最大化したいです。 しかし、彼にとってこの仕事は難しいので、あなたが彼の代わりに表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を求めてください。

Input

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

W
N K
A_1 B_1
A_2 B_2
:
A_N B_N

• $1$ 行目には、表計算ソフトの幅 $W (1 ≦ W ≦ 10000)$ が与えられる。
• $2$ 行目には、スクリーンショットの数 $N (1≦N≦50)$ と、表計算ソフトに貼り付け可能なスクリーンショットの枚数 $K(1≦K≦N)$ が、スペース区切りで与えられる。
• $3$ 行目から $N$ 行では、各スクリーンショットに関する情報が与えられる。このうち $i$ 行目では $i$ 番目のスクリーンショットにおける、幅 $A_i (1 ≦ A_i ≦ 1000)$ と、重要度 $B_i (1 ≦ B_i ≦ 100)$ の値が、スペース区切りで与えられる。

Output

表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を $1$ 行で出力せよ。出力の末尾には改行をいれること。