All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

B. Monster Gouketsu
/

Binary Search, Math

Problem
Editorial
Analytics

Gouketsu has been kidnapped by the monsters. But seeing his amazing martial arts skills, they have given him the chance to be an executive member of the Monster Association. They have given him \(M\) monster cells, while Gouketsu has \(N\) natural cells. He wants to monsterize all of his natural cells (to become the strongest monster), but alas, there are some conditions! He can monsterize a natural cell at the cost of \(X\) monster cells and destroy a natural cell to get \(Y\) monster cells (note that he cannot destroy an already monsterized cell).

Since Gouketsu has been blinded by greed and cannot think of an optimal solution, help him calculate the maximum amount of natural cells that he can monsterize.

Input

First line of input contains \(T\) - the number of testcases.

Each testcase contains only one line with \(4\) integers: \(M, N, X, Y\)

Output

For each testcase, print a single integer - the maximum number of natural cells that Gouketsu can monsterize..

Constraints

\(1 \le T \le 5\)

\(1 \le M, N, X, Y \le 10^9 ​​\)

SAMPLE INPUT
3
10 5 2 1
11 5 2 1
9 5 2 1
SAMPLE OUTPUT
5 
5
4
Explanation

Test case 1: He can monsterize all his \(5\) natural cells at the cost of \(10\) monster cells (\(2\) monster cells each for a natural cell).

Test case 3: He can monsterize only \(4\) of his natural cells at the cost of \(8\) monster cells.

 

Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?