TopCoder

User's AC Ratio

47.8% (11/23)

Submission's AC Ratio

13.1% (20/153)

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)
0 2000 65536
1 2000 65536
2 2000 65536
3 2000 65536
4 2000 65536
5 2000 65536
6 2000 65536
7 2000 65536
8 2000 65536
9 2000 65536
10 2000 65536
11 2000 65536
12 2000 65536
13 2000 65536
14 2000 65536
15 2000 65536
16 2000 65536