您正在使用伤害为 $$$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$$$ 硬币。