問題文

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

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

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

入力

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

$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)$ の値が、スペース区切りで与えられる。

出力

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

入力例1

10
3 2
4 20
3 40
6 100

出力例1

140

$2$ 番目と $3$ 番目のスクリーンショットを選ぶと、合計の幅が $9$ 、使用するスクリーンショットが $2$ 枚となり、条件を満たす。 この時の重要度の和は、 $40 + 100$ で $140$ となる。

入力例2

10
5 4
9 10
3 7
3 1
2 6
4 5

出力例2

18

必ず $K$ 枚のスクリーンショットを使わなくても良いことに注意してください。

入力例3

22
5 3
5 40
8 50
3 60
4 70
6 80

出力例3

210

幅が足りていても、スクリーンショットを最大で $K$ 枚までしか置けないことに注意してください。