EIUASSEMBLY  Assembly line
The Alternate Control Machine (ACM) Factory has a large assembly line to make a type of product. The assembly has N robots (R_{1}, R_{2}...R_{N}) working sequentially. That means a semifinished product moves from robot R_{1}, to R_{2}, then to R_{3}... to R_{N}. Each robot adds a component to the product. Each robot can complete its own job in P_{i} products per one hour.
The company has a budget of M VNĐ to improve productivity for the entire assembly. As a product director, you know that robot R_{i} needs to invest M_{i} VNĐ to contribute to the production of one more product per hour. You have to optimize the amount of money to invest to each robot to produce maximum number of products per hour.
Input
The first line of input contains one integer T (1≤T≤10)  the number of test cases.
Then T test cases are given as follows:
 The first line of each test case contains an integer N (1≤n≤10^{5}) and an integer M (0≤M≤10^{12}) – the number of robots and the budget
 Line ith of the next N lines contains two integers P_{i }(1≤P_{i}≤10^{9}) and M_{i} (1≤M_{i}≤10^{9}) – information of the robot ith
Output
For each test case, output in one line the maximum number of products the assembly can make after investing at most M VNĐ.
Example
Input: 1 3 7 1 2 2 3 3 1 Output: 3
hide comments
aknov711:
20200813 09:15:23
Getting WA on test case1. 

marethyu1:
20190328 23:25:59
@pratjosh9: we could spend (2 x $2) on first robot to increase its productivity by 2 and spend $3 on second robot to increase its productivity by 1. Now all robots can make up to 3 products per hour and total money spend = $2 + $2 + $4= $7 

pallindromeguy:
20180314 22:04:00
@mohinem: your test case gives overflow on cpp but the solution still gets AC. Last edit: 20180314 22:04:15 

chawlaroxx_06:
20171231 10:27:15
TLE in PYTHON and AC in PYPY , same code :D


pratjosh9:
20171217 06:13:36
could anyone explain the sample test case? 

viratian_070:
20170620 12:56:26
very good question....game is to find upperbound 

bnzhaxx:
20170424 23:40:49
The input is not sorted. 

kasiekdec:
20170314 09:40:59
I do not understand the input  can we assume that Pi are sorted and there are no duplicates? 

aman224:
20170308 11:24:49
Just take care of overflows , by deciding the lower and upper bounds correct 

kapillamba4:
20170131 12:22:01
0.14 seconds using map Last edit: 20170928 13:02:50 
Added by:  Ha Minh Ngoc 
Date:  20160512 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: GOSU 