GAMIN ARENA

 

Elgin and Hajee are planning to conduct gamindrome next day. As they have to connect all the computers, they need lan cables, hubs and wireless routers. They went to Richi street to purchase them. Unexpectedly hub was not available in any shop.

Any lan cable can connect two computers. Any wireless router can connect atmost ‘k’ number of computers. Any computer can be connected to atmost one lan cable and atmost one wireless network. If a computer is connected to both lan and wireless, the connections get automatically bridged.

 

They have n computers and their aim is to connect all the computers with minimum cost. So they have to buy minimum number of lan cables and wireless routers.

The cost of of buying one lan cable is L and the cost of buying one wireless router is W. 

Given n, k, L and W find the minimum cost needed to connect all the computers.

 

Input Specification:

The first line contains an integer t, the number of test cases. Each test case consists 4 integers n, k, L and W as defined above.

 

Output Specification:

For each test case find the minimum cost to connect all the computers.

Input Constraints:

1<=t<=1000

1<=n<=1000

2<=k<=1000

1<=L<=1000

1<=W<=1000

 

Sample Input: 

 9

1 4 8 6

10 2 5 8

5 4 9 9

2 5 2 6

7 3 3 6

3 3 3 5

6 4 7 2

10 4 2 7

5 3 10 8

Sample Output:

0

57

18

2

18

5

11

20

26