1774 . Ch3. Section 9. 妁艷的頭髮
TopCoder
Tags
Description
終於，妁艷把鎖解開了。呼~，終於可以回家了，妁艷如釋重負的嘆了一口氣。
「噢！！」「笨葛格！怎麼拖這麼久！」妹妹嘟著嘴快哭了的扯著妁艷的頭髮。
「你剛剛不是很高興被救嗎？怎麼現在......噢！！」
原來妹妹對於妁艷這麼晚才來救她感到十分的不滿。好不容易可以回家，當然要高高興興的，因此妁艷要想辦法讓妹妹高興起來。
妁艷有N種方法讓妹妹高興，每種方法可以增加妹妹的高興度Hi，會消耗妁艷的魔力Ci。而在經過這一連串的事件後，妁艷只剩下M的魔力了。
請問妁艷最多可以讓妹妹的高興度增加多少呢？
Input Format
輸入的第一行有兩個正整數N , M。
第2 ~ N + 1行每行有兩個正整數Hi、Ci。
N , M ≤ 2,000
Hi , Ci ≤ 109
Output Format
請輸出一個整數代表妹妹的高興度的最大增加量。
Sample Input 1
3 10
1 5
3 3
3 2
1 5
3 3
3 2
Sample Output 1
15
Hints
「拉的到你就來啊咧~」 - 妁艷對於想拉他頭髮的人的看法
Problem Source
原TIOJ1774 / problem setter : esrever
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |