/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
高橋君は医者のすぬけ君から N 種類の薬を処方されました。i 種類目の薬は(処方された日を含めて) a_i 日間、毎日 b_i 錠ずつ飲む必要があります。また、高橋君はこれ以外の薬を飲む必要がありません。
薬を処方された日を 1 日目とします。1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのは何日目かを求めてください。
制約
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 b_1 \vdots a_N b_N
出力
1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのが X 日目の時、 X を出力せよ。
入力例 1
4 8 6 3 2 5 1 9 4 2
出力例 1
3
1 日目には、高橋君は 1,2,3,4 種類目の薬をそれぞれ 3,5,9,2 錠飲む必要があります。よってこの日は 19 錠飲む必要があり、K(=8) 錠以下ではありません。
2 日目には、高橋君は 1,2,4 種類目の薬をそれぞれ 3,5,2 錠飲む必要があります。よってこの日は 10 錠飲む必要があり、K(=8) 錠以下ではありません。
3 日目には、高橋君は 1,4 種類目の薬をそれぞれ 3,2 錠飲む必要があります。よってこの日は 5 錠飲む必要があり、初めて K(=8) 錠以下になります。
以上より、3 が答えです。
入力例 2
4 100 6 3 2 5 1 9 4 2
出力例 2
1
入力例 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
出力例 3
492686569
Score : 350 points
Problem Statement
Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.
Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?
Constraints
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K a_1 b_1 \vdots a_N b_N
Output
If Takahashi has to take K pills or less on day X for the first time on or after day 1, print X.
Sample Input 1
4 8 6 3 2 5 1 9 4 2
Sample Output 1
3
On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.
Thus, the answer is 3.
Sample Input 2
4 100 6 3 2 5 1 9 4 2
Sample Output 2
1
Sample Input 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
Sample Output 3
492686569