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 at most ‘k’ number of computers. Any computer can be connected to at most one LAN cable and at most 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

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

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

Constraints

1 <= t <= 1000

1 <= n <= 1000

2 <= k <= 1000

1 <= L <= 1000

1 <= W <= 1000

Example

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

Output:
0
57
18
2
18
5
11
20
26