97模擬 Problem 7 (奧步戰術

在黑暗算法界中，使用奧步解題似乎已經漸漸成為主流。雖然使用奧步將漸漸使人走向魔路，最後被內心的虛無吞噬，不過這不是今天的問題。考慮在某個考試中，有n 道題目，而總答題時間為T。對於每題都只有三種可能：

1. 正解能得到全對的分數(得2 分)

2. 奧步能拿到半對(得1 分)

3. 放棄的話當然就沒分囉(0 分)

而對每題來說，要達到這三種分數所需花的時間皆不同，所有題目拿0 分都不用花費時間；在題目i 使用奧步拿半對所需時間為Hi，要寫正解所需時間為Ci，其中對於任何題目i，必有滿足0。試問：在時間T 內，用最佳的答題方式，最多可以拿幾分？

輸入說明：

輸入檔第一行說明有幾組測試資料，第二行有兩個整數n 和T，分別代表有幾題，以及總作答時間。接下來n 行每行有兩個整數Ci 和Hi，代表第i 題寫正解需要時間Ci，寫奧步需要時間Hi。其中：

• 題目總數n≤100000
• 答題所需時間1≤Hi，Ci≤1000000
• 總作答時間0＜， T≤1000000000



輸出說明：

每個測試範例請輸出一個整數，代表最大得分。

輸入範例：

2
5 12
4 3
6 2
5 3
4 3
5 2
4 10
5 3
6 5
3 1
4 3
輸出範例：
6
5