TopCoder

Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

53.8% (21/39)

Submission's AC Ratio

17.4% (50/288)

Tags

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12
12 2000 65536 262144 13
13 2000 65536 262144 14
14 2000 65536 262144 15
15 2000 65536 262144 16
16 2000 65536 262144 17