D - 高橋くんの苦悩 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。 画面のスクリーンショットは 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 枚までしか置けないことに注意してください。