← 返回题目列表

Codeforces · 2035/E

E. 怪物

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

您正在使用伤害为 $$$d$$$ 的武器与生命值为 $$$z$$$ 的怪物战斗。最初,$$$d=0$$$。您可以执行以下操作。

- 增加$$$d$$$——你的武器伤害$$$1$$$,花费$$$x$$$金币。
- 攻击怪物,造成 $$$d$$$ 伤害并花费 $$$y$$$ 硬币。

您不能连续执行第一个操作超过 $$$k$$$ 次。

找出通过造成至少 $$$z$$$ 伤害来击败怪物所需的最少金币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。

每个测试用例的唯一行包含 4 个整数 $$$x$$$、$$$y$$$、$$$z$$$ 和 $$$k$$$ ($$$1\leq x, y, z, k\leq 10^8$$$) — 第一个操作的成本、第二个操作的成本、怪物的生命值以及第一个操作的限制。

输出

对于每个测试用例,输出击败怪物所需的最少硬币数量。

示例

输入 #1

4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10

输出 #1

12
190
280
160

注意

在第一个测试用例中,$$$x = 2$$$、$$$y = 3$$$、$$$z = 5$$$ 和 $$$k = 5$$$。以下是实现 $$$12$$$ 硬币成本最低的策略:

- 伤害增加 $$$1$$$,花费 $$$2$$$ 硬币。
- 伤害增加 $$$1$$$,花费 $$$2$$$ 硬币。
- 伤害增加 $$$1$$$,花费 $$$2$$$ 硬币。
- 攻击怪物,造成 $$$3$$$ 伤害,花费 $$$3$$$ 硬币。
- 攻击怪物,造成 $$$3$$$ 伤害,花费 $$$3$$$ 硬币。

你总共造成 $$$3 + 3 = 6$$$ 伤害,击败了生命值为 $$$5$$$ 的怪物。您使用的硬币总数为 $$$2 + 2 + 2 + 3 + 3 = 12$$$ 硬币。

在第二个测试用例中,$$$x = 10$$$、$$$y = 20$$$、$$$z = 40$$$ 和 $$$k = 5$$$。这是一个以尽可能低的成本获得 $$$190$$$ 硬币的策略:

- 伤害增加 $$$5$$$,花费 $$$5\cdot x$$$ = $$$50$$$ 硬币。
- 攻击怪物一次,造成 $$$5$$$ 伤害,花费 $$$20$$$ 金币。
- 伤害增加 $$$2$$$,花费 $$$2\cdot x$$$ = $$$20$$$ 硬币。
- 攻击怪物$$$5$$$次,造成$$$5\cdot 7 = 35$$$伤害,消耗$$$5\cdot y$$$ = $$$100$$$金币。

你总共造成 $$$5 + 35 = 40$$$ 伤害,击败了生命值恰好为 $$$40$$$ 的怪物。您使用的硬币总数为 $$$50 + 20 + 20 + 100 = 190$$$ 硬币。