← 返回题目列表

Codeforces · 1793/A

A. 又一次促销

中文机器翻译题面 查看原题

著名商店“第二食品”每月只有两天出售杂货。而且每天的价格都不一样。您想购买 $$$n$$$ 公斤土豆一个月。您知道该月的第一天 $$$1$$$ 公斤土豆需要 $$$a$$$ 硬币,第二天则需要 $$$b$$$ 硬币。在“第二食品”中,您可以购买任意整数公斤的土豆。

幸运的是,“第二食”宣布了土豆促销活动,仅在每月的第一天有效——每购买 $$$m$$$ 公斤土豆,即可获得 $$$1$$$ 公斤作为礼物!换句话说,支付 $$$m$$$ 公斤即可获得 $$$m + 1$$$ 公斤。

求出购买至少 $$$n$$$ 公斤土豆所需花费的最少金币数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$a$$$ 和 $$$b$$$ $$$(1 \leq a, b \leq 10^9)$$$ — 分别是第一天和第二天 $$$1$$$ 公斤土豆的价格。

第二行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1 \leq n, m \leq 10^9)$$$ — 需要购买的土豆数量和使用促销活动的土豆数量。

输出

对于每个测试用例,打印一个整数 - 购买至少 $$$n$$$ 公斤土豆所需支付的最小硬币数量。

示例

输入 #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

注意

在第一个测试用例中,第一天您购买 $$$1$$$ 公斤,并获得额外 $$$1$$$ 的促销优惠。第二天,你可以买 $$$1$$$ 公斤土豆。因此,您总共将花费 $$$5+4=9$$$ 硬币。

在第二个测试用例中,第一天您购买了 $$$2$$$ 公斤,并获得了另外 $$$1$$$ 的促销优惠。这样您将花费 $$$2 \cdot 5 = 10$$$ 硬币。