AT_abc015_4 [ABC015D] 高橋くんの苦悩

# 题目大意 你有 $N$ 个物品，第 $i$ 个物品的重量为 $A_i$ ，体积为 $1$ ，价值为 $B_i$ ，你还有一个背包，背包的容积为 $K$ ，所能承受的最大重量为 $W$ ，现在你要将一些物品放入背包中，求放入背包的物品的最大价值。

输入共三行。 第一行输入一个数 $W(1\le W\le10000)$ ，表示背包所能承受的最大重量。 第二行输入两个数 $N,K(1\le K\le N\le50)$ ，表示物品的数量和背包的容积。 剩下的 $n$ 行分别输入两个数 $A_i,B_i(1\le A_i\le1000,1\le B_i\le100)$ ，表示第 $i$ 个物品的重量和价值。

一个数 $ans$ ，表示放入背包的物品的最大价值。

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