Question
Lamp Purchase Optimization
Sam is setting up a cozy reading nook and wants to fill it with exactly N lamps. He loves the warm glow of red lamps, but blue lamps are a bit cheaper. To keep the vibe he wants, Sam needs at least K of the lamps to be red. With red lamps costing X rupees each and blue lamps Y rupees each, what’s the minimum amount Sam has to spend to create his perfect setup?
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of a single line containing four space-separated integers N, K, X, Y.
Constraints
1 ≤ T ≤ 103
1 ≤ N ≤ 108
0 ≤ K ≤ N
1 ≤ X, Y ≤ 10
Each test case consists of a single line containing four space-separated integers N, K, X, Y.
Constraints
1 ≤ T ≤ 103
1 ≤ N ≤ 108
0 ≤ K ≤ N
1 ≤ X, Y ≤ 10
Output
For each test case, output on a new line the minimum amount of money Sam needs to pay in order to buy N lamps such that at least K of the lamps bought are red.
Example
Sample Input
4
2 2 5 1
4 1 3 1
3 0 4 7
5 2 3 4
Sample Output
10
6
12
15
Explanation
Sam buys 2 red lamps with 2 x 5 = 10 rupees.
Sam buys 1 red lamp and 3 blue lamps with 1 x 3 + 3 x 1 = 6 rupees.
Sam buys 3 red lamps with 3 x 4 = 12 rupees.
4
2 2 5 1
4 1 3 1
3 0 4 7
5 2 3 4
Sample Output
10
6
12
15
Explanation
Sam buys 2 red lamps with 2 x 5 = 10 rupees.
Sam buys 1 red lamp and 3 blue lamps with 1 x 3 + 3 x 1 = 6 rupees.
Sam buys 3 red lamps with 3 x 4 = 12 rupees.