144 . 高棕櫚農場2
TopCoder
Description
円円實在太會精打細算了，使得高棕櫚農場主人每次看到他光顧都會心裡暗罵一番，想說今天又要虧本了 (前情提要請見「高棕櫚農場」題目)。有天，在円円準備開始大吃特吃之前，農場主人為了不要賠太多，給了他另外一個限制：不能吃掉超過 $K$ 個高棕櫚。這時円円雖然感覺被黑了，這樣跟本就不是吃到飽了嘛，但當下的目標還是要吃掉高棕櫚獲得最大的滿足感。請問円円最多能獲得多少滿足感呢？
Input Format
第一行為一個正整數 $T$ ，$T \leq 10$ ，表示共有 $T$ 筆測資。
每筆測資第一行為三個正整數 $N$, $M$, $K$ ，表示高棕櫚的數量、円円可以承受的飽足感上限，還有吃掉高棕櫚數量的上限，$1 \leq K \leq N \leq 100$，$1 \leq M \leq 1000$ 。
接著 $N$ 行，每行為兩個正整數 $A_i$ 和 $B_i$，表示吃掉第 $i$ 個高棕櫚可以獲得的飽足感與滿足感，$1 \leq A_i \leq 100$，$1 \leq B_i \leq 1000000$。
對於 30% 的測資， $K = N$ 。
Output Format
對於每筆測資，輸出円円可以獲得的滿足感最大值。
Sample Input 1
2
3 6 3
2 4
3 5
4 6
3 9 2
2 4
3 5
4 6
3 6 3
2 4
3 5
4 6
3 9 2
2 4
3 5
4 6
Sample Output 1
10
11
11
Hints
Problem Source
NEOJ Problem 158
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 30 | |
| 2 | 1 | 30 | |
| 3 | 2 | 40 |