The famous store "Second Food" sells groceries only two days a month. And the prices in each of days differ. You wanted to buy $n$ kilos of potatoes for a month. You know that on the first day of the month $1$ kilo of potatoes costs $a$ coins, and on the second day $b$ coins. In "Second Food" you can buy any integer kilograms of potatoes.

Fortunately, "Second Food" has announced a promotion for potatoes, which is valid only on the first day of the month — for each $m$ kilos of potatoes you buy, you get $1$ kilo as a gift! In other words, you can get $m + 1$ kilograms by paying for $m$ kilograms.

Find the minimum number of coins that you have to spend to buy at least $n$ kilos of potatoes.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). Description of the test cases follows.

The first line of each test case contains two integers $a$ and $b$ $(1 \leq a, b \leq 10^9)$ — the prices of $1$ kilo of potatoes on the first and second days, respectively.

The second line contains two integers $n$ and $m$ $(1 \leq n, m \leq 10^9)$ — the required amount of potatoes to buy and the amount of potatoes to use the promotion.

For each test case print one integer — the minimum number of coins that you have to pay to buy at least $n$ kilos of potatoes.