CF2035E.Monster

这个原神 Boss 太难打了。幸好他们有 $6$ 个金币只需 $4.99$ 美元的充值包。我得小心点，花的钱不能太多，不然我妈会发现……

你正在用一把伤害为 $d$ 的武器与一个生命值为 $z$ 的怪物战斗。初始时，$d=0$。你可以进行以下两种操作：

• 将武器的伤害 $d$ 增加 $1$，花费 $x$ 个金币。
• 攻击怪物，造成 $d$ 点伤害，花费 $y$ 个金币。

你不能连续进行第一种操作超过 $k$ 次。

请你计算，至少需要多少金币才能通过造成至少 $z$ 点伤害击败怪物。

第一行包含一个整数 $t$（$1\le t\le 100$），表示测试用例的数量。

每个测试用例包含一行，包含四个整数 $x$、$y$、$z$ 和 $k$（$1\leq x, y, z, k\leq 10^8$），分别表示第一种操作的花费、第二种操作的花费、怪物的生命值和第一种操作的连续次数限制。

对于每个测试用例，输出击败怪物所需的最小金币数。

在第一个测试用例中，$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$ 次，每次造成 $7$ 点伤害，共造成 $5\cdot 7=35$ 点伤害，花费 $5\cdot y=100$ 金币。

你总共造成了 $5+35=40$ 点伤害，刚好击败生命值为 $40$ 的怪物。总共花费了 $50+20+20+100=190$ 金币。

由 ChatGPT 4.1 翻译