AT_abc015_4 [ABC015D] 高橋くんの苦悩

[problemUrl]: https://atcoder.jp/contests/abc015/tasks/abc015_4 高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。 画面のスクリーンショットは $ 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 $ 行で出力せよ。出力の末尾には改行をいれること。

### Sample Explanation 1 $ 2 $ 番目と $ 3 $ 番目のスクリーンショットを選ぶと、合計の幅が $ 9 $ 、使用するスクリーンショットが $ 2 $ 枚となり、条件を満たす。 この時の重要度の和は、 $ 40\ +\ 100 $ で $ 140 $ となる。 ### Sample Explanation 2 必ず $ K $ 枚のスクリーンショットを使わなくても良いことに注意してください。 ### Sample Explanation 3 幅が足りていても、スクリーンショットを最大で $ K $ 枚までしか置けないことに注意してください。