題目描述

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.

著名商店「Second Food」每個月只有兩天出售雜貨，而每天的價格都不同。您想要購買 n 公斤的馬鈴薯供一個月使用。您知道在每個月的第一天，1 公斤馬鈴薯的價格是 a 枚硬幣，而在第二天是 b 枚硬幣。在「Second Food」店裡，您可以購買任意整數公斤的馬鈴薯。

幸運的是，「Second Food」宣布了一個馬鈴薯促銷活動，僅在每個月的第一天有效-每購買 m 公斤的馬鈴薯，您將獲得 1 公斤作為禮物！換句話說，您可以支付 m 公斤的價錢，獲得 m+1 公斤的馬鈴薯。

找出您至少需要花費的最少硬幣數量，以購買至少 n 公斤的馬鈴薯。

輸入格式

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10000). Description of the test cases follows.

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

The second line contains two integers n and m (1≤n,m≤10⁹) — the required amount of potatoes to buy and the amount of potatoes to use the promotion.

每個測試包含多個測試案例。第一行包含測試案例的數量 t (1≤t≤10000)。接下來是每個測試案例的描述。

每個測試案例的第一行包含兩個整數 a 和 b (1≤a,b≤10⁹) — 分別代表第一天和第二天每公斤馬鈴薯的價格。

第二行包含兩個整數 n 和 m (1≤n,m≤10⁹) — 分別代表需要購買的馬鈴薯數量和使用促銷活動的馬鈴薯數量。

輸出格式

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.

對於每個測試案例，請輸出一個整數，該整數表示購買至少 n 公斤馬鈴薯所需支付的最少硬幣數量。

Samples

5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8

9
10
9
135
888888888900000000

提示

In the first test case, on the first day you buy 1 kilo and get 1 more for a promotion. On the second day, you can buy 1 kilo of potatoes. Thus, you will spend 5+4=9 coins in total.

In the second test case, on the first day you buy 2 kilo and get another 1 more for a promotion. This way you will spend 2⋅5=10 coins.

根據您提供的第一個測試案例，第一天您購買 1 公斤並享受促銷活動獲得 1 公斤，第二天您可以購買 1 公斤馬鈴薯。因此，您總共需要支付 5+4=9 枚硬幣。

根據您提供的第二個測試案例，第一天您購買 2 公斤並享受促銷活動獲得額外的 1 公斤。這樣您需要支付 2⋅5=10 枚硬幣。

原始資料

• Zero1 題號：b117
• Hydro 題號：Z1117
• Locale：zh_TW
• Display：practice