CF1793A.Yet Another Promotion
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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≤t≤10000 ). Description of the test cases follows.
The first line of each test case contains two integers a and b (1≤a,b≤109) — 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≤109) — 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.
输入输出样例
输入#1
5 5 4 3 1 5 4 3 2 3 4 3 5 20 15 10 2 1000000000 900000000 1000000000 8
输出#1
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.