1719 測資加強 已 rejudge
1318 . 奥步戰術 Tactic
TopCoder
Description
在黑暗算法界中，使用奧步解題似乎已經漸漸成為主流。
雖然使用奧步將漸漸使人走向魔路，最後被內心的虛吞噬，不過這不是今天的問題。
考慮在某個考試中，有n道題目，而總答題時間為T。
對於每題都只有三種可能
正解能得到全對的分數(得2分)、奧步能拿到半對(得1分)、放棄的話當然就沒分囉(0分)。
而對每題來說，要達到這三種分數所需花的時間皆不同
所有題目拿0分都不用花費時間；在題目i使用奧步拿半對所需時間為Hi，要寫正解所需時間為Ci
其中對於任何題目i，必有滿足0<Hi<Ci。
試問：在時間T內，用最佳的答題方式，最多可以拿幾分？
Input Format
第一行有兩個整數n和t
分別代表有幾題，以及總作答時間
接下來n行每行有兩個整數Ci和Hi
代表第i題寫正解需要時間Ci, 寫奧步需要時間Hi
題目總數n<=100,000
答題所需時間1<=Hi, Ci<=1,000,000
總作答時間0<T<=1,000,000,000
Output Format
輸出一個整數，代表最大得分
Sample Input 1
5 12
4 3
6 2
5 3
4 3
5 2
4 3
6 2
5 3
4 3
5 2
Sample Output 1
6
Hints
Problem Source
原TIOJ1318 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 20 |