143 . 高棕櫚農場
TopCoder
Description
由於經濟不景氣，專門栽種高棕櫚的農夫們也漸漸撐不下去，有些後來轉型成為觀光農場，介紹高棕櫚是如何培育的，有些則是祭出「XXX 元吃到飽」的優惠方案吸引遊客。有天円円來到了一間可以吃到飽的農場，為了回本當然要吃得盡量過癮啦！
然而，円円追求的不是吃得飽而是吃得滿足，注意這兩者是不一樣的，有些高棕櫚雖然很有飽足感，味道卻不怎麼樣，「滿足感」當然就比較低，由於円円的為容量有限，不可能吃掉所有的高棕櫚，因此他希望在不吃到撐的前提下獲得盡量大的滿足感。円円進到吃到飽專區後，發現裡面總共有 $N$ 個高棕櫚，接著他分析了一下每個高棕櫚，得到個別的「飽足感」和「滿足感」。請問円円最多可以獲得多少滿足感呢？
Input Format
第一行為一個正整數 $T，T ≤ 10$ ，表示共有 $T$ 筆測資。
每筆測資第一行為兩個正整數 $N, M$ ，表示高棕櫚的數量及円円可以承受的飽足感上限，$1 \le N \le 100，1 \le M \le 1000000$ 。
接著 $N$ 行，每行為兩個正整數 $A_i, B_i$ ，表示吃掉第 $N$ 個高棕櫚可以獲得的飽足感與滿足感，$1 \le Ai \le 100000，1 \le Bi \le 100$ 。
對於 30% 的測資，$A_i \le 100$
Output Format
對於每筆測資，輸出円円在飽足感不超過 $M$ 時能獲得的滿足感最大值。
Sample Input 1
2
2 5
2 4
3 3
2 4
2 4
3 3
2 5
2 4
3 3
2 4
2 4
3 3
Sample Output 1
7
4
4
Hints
Problem Source
NEOJ Problem 157
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0, 2 | 30 | |
| 2 | 0~3 | 70 |