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 (R1, R2 ... RN) working sequentially. That means a semi-finished product moves from robot R1, to R2, then to R3 ... to RN. Each robot adds a component to the product. Each robot can complete its own job in Pi 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 Ri needs to invest Mi 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 ≤ 105) and an integer M (0 ≤ M ≤ 1012) – the number of robots and the budget
  • Line i-th of the next N lines contains two integers Pi (1 ≤ Pi ≤ 109) and Mi (1 ≤ Mi ≤ 109) – information of the robot i-th

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

Hint: You should check for the case: company budget is 0, or cannot upgrade any robot at all. This is the visualization explain why you should check if you use binary search to solve.


hide comments
kapillamba4: 2017-01-31 12:22:01

0.14 seconds using map

Last edit: 2017-09-28 13:02:50
vengatesh15: 2017-01-24 18:35:30

Take care about the upper bound that cost me 1 WA...

in_arena: 2017-01-03 09:49:51

good one !! 50th

Chinmay Kousik: 2016-11-26 13:37:08

My code is getting the correct answer on randomly generated test cases but WA here. Please help. submission id: 18262733

pawan161096: 2016-08-30 09:03:46

try this test case : answer is 251
1
5 1000000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1000000000 1

Last edit: 2016-08-30 09:04:00
mohinem: 2016-08-28 19:49:12

try this test case -- > ans -- >1e9 + 1e3
1
1 1000000000000
1000000000 1000000000

Last edit: 2016-08-28 20:13:15
dwij28: 2016-08-28 12:21:54

I could not do it in C++, getting wrong answer perhaps due to long long integer overflow, maybe because I chose a larger upper bound than the question needs. Overflows are irritating . Solved it in Python anyways.

Shubham Pandey: 2016-07-05 22:08:05

nice application of binary search

aashray: 2016-06-28 22:16:41

nice problem to solve using binary search...easy one..heart of the solution is to judge the upper bound and the lower bound

Ha Minh Ngoc: 2016-06-11 16:28:31

@lt: let check the upper bound value in your solution


Added by:Ha Minh Ngoc
Date:2016-05-12
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU