Мужик, этот босс в Genshin такой сложный. Хорошо, что у них есть пополнение на \(6\) монет всего за \( \$4.99\). Мне следует быть осторожнее и не тратить больше, чем нужно, иначе мама меня поймает...
Вы сражаетесь с монстром со здоровьем \(z\), используя оружие с уроном \(d\). Изначально \(d=0\). Вы можете выполнять следующие действия.
- Увеличить \(d\) — урон вашего оружия на \(1\), потратив \(x\) монет.
- Атаковать монстра, нанеся ему \(d\) урона, потратив \(y\) монет.
Вы не можете выполнять первую операцию более \(k\) раз подряд.
Найдите минимальное количество монет, необходимое для того, чтобы победить монстра, нанеся ему хотя бы \(z\) урона.
Выходные данные
Для каждого набора входных данных выведите минимальное количество монет, необходимое для победы над монстром.
Примечание
В первом наборе входных данных \(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\) монет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10
|
12
190
280
160
|