D. Рудольф и выпекание булочек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кондитерская «Слойки на вынос» всегда имеет большое количество заказов. Для изготовления слоек используется Автоматическая Машина Выпечки Х (АМВ Х), которая может изготовить одну слойку за $$$t_0$$$ минут.

Со временем машина стала барахлить и теперь может изготовить подряд только $$$b$$$ слоек, после чего должна «отдохнуть» $$$k$$$ минут. После «отдыха» машина может снова испечь до $$$b$$$ слоек, потом ей надо снова «отдохнуть» и т.д.

Чтобы не терять клиентуру из-за невозможности выполнить заказы в срок, хозяйка кондитерской, Ванесса, приобрела $$$n$$$ новых Автоматических Машин Выпечки ХХ (АМВ ХХ), которые могут работать круглосуточно без перерыва. $$$i$$$-я новая машина может изготовлять одну слойку за $$$t_i$$$ минут. Все машины могут работать одновременно.

При наличии одной машины для выпечки Ванесса могла легко подсчитать время, необходимое на выпекание необходимого числа слоек. С новыми машинами расчеты стали труднее, и Ванесса попросила Рудольфа составить для неё программу.

Рудольф последнее время сильно занят и делегирует просьбу Ванессы вам.

Дано $$$s$$$  — количество слоек в заказе. Ванесса и Рудольф хотят знать, за какое минимальное время можно выполнить заказ, используя все или некоторые, имеющиеся в распоряжении, Автоматические Машины Выпечки?

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

Первая строка входных данных содержит три целых неотрицательных числа, характеризующих АМВ Х: $$$t_0$$$, $$$b$$$, $$$k$$$ ($$$1 \le t_0 \le 10^5$$$, $$$1 \le b \le 10^5$$$, $$$1 \le k \le 10^5$$$).

Вторая строка содержит целое неотрицательное число $$$n$$$ ($$$0 \le n \le 10^5$$$) — число новых машин для выпечки, купленных Ванессой.

Третья строка содержит $$$n$$$ целых неотрицательных чисел $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$1 \le t_i \le 10^5, 1 \le i \le n$$$)  — время, за которое каждая новая машина изготавливает одну слойку. .

Четвертая строка содержит число $$$s$$$ ($$$0 \le s \le 10^9$$$)  — количество слоек в заказе.

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

Выведите одно целое число — минимальное время в минутах, за которое можно выполнить весь заказ.

Примеры
Входные данные
5 20 30
2
10 12
10
Выходные данные
30
Входные данные
5 7 23
0
3
Выходные данные
15
Примечание

В первом примере на выпекание $$$10$$$ слоек на имеющихся в распоряжении Ванессы трех Автоматических Машинах Выпечки потребуется не менее $$$30$$$ минут. Машины для выпечки могут быть использованы, например, следующим образом:

  • на АМВ Х за $$$30$$$ минут будет изготовлено $$$6$$$ слоек;
  • на $$$1$$$-й новой АМВ ХХ будет изготовлено $$$3$$$ слойки;
  • на $$$2$$$-й новой АМВ ХХ — $$$1$$$ слойка.
Можно распределить выпекание булочек по машинам и другим образом, но, в любом случае, не получится потратить меньше $$$30$$$ минут.

Во втором примере в распоряжении Ванессы имеется только одна машина для выпечки. На изготовлении трех слоек потребуется $$$5 \times 3 = 15$$$ минут.