E. Монстр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Мужик, этот босс в Genshin такой сложный. Хорошо, что у них есть пополнение на $$$6$$$ монет всего за $$$ \$4.99$$$. Мне следует быть осторожнее и не тратить больше, чем нужно, иначе мама меня поймает...

Вы сражаетесь с монстром со здоровьем $$$z$$$, используя оружие с уроном $$$d$$$. Изначально $$$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$$$) — стоимость первой операции, стоимость второй операции, здоровье монстра и ограничение на первую операцию.

Выходные данные

Для каждого набора входных данных выведите минимальное количество монет, необходимое для победы над монстром.

Пример
Входные данные
4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10
Выходные данные
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$$$ монет.