TopCoder

Thumb rem
EGOIST
如果真愛有顏色,那麼一定是藍色的!

User's AC Ratio

45.5% (10/22)

Submission's AC Ratio

12.3% (19/154)

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

5 12
4 3
6 2
5 3
4 3
5 2

Sample Output

6

Hints

Problem Source

原TIOJ1318 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536
10 2000 65536 65536
11 2000 65536 65536
12 2000 65536 65536
13 2000 65536 65536
14 2000 65536 65536
15 2000 65536 65536
16 2000 65536 65536