D - 高橋くんの苦悩
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは、ソフトウエアが期待通りに動いたというエビデンス(証拠)として、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。 画面のスクリーンショットは N 枚あり、高さは全て等しいのですが、幅が異なります。 また、表計算ソフトに貼りつけ可能なスクリーンショットには 2 つの制約が存在します。
- 表計算ソフトの幅は W しかない。そのため、貼りつけるスクリーンショットの幅の合計値は W 以下でなければならない。
- 表計算ソフトは 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 枚までしか置けないことに注意してください。