На каникулах Роман решил отдохнуть во Флатландии и арендовал себе апартаменты и роскошный автомобиль. Разумеется, такой автомобиль нельзя оставлять во дворе, поэтому Роман хочет также арендовать место на ближайшей охраняемой парковке. Поскольку он уже поиздержался с жильём и машиной, он хочет потратить на парковку как можно меньше бурлей.
На парковке доступны три тарифа аренды:
Роман планирует отдыхать во Флатландии n дней. Любой тариф можно использовать произвольное количество раз, также можно арендовать парковку на суммарно больший срок, чем нужно. Какое минимальное количество бурлей придётся заплатить Роману, чтобы иметь возможность использовать стоянку все n дней?
Первая строка входных данных содержит три целых числа a, b, c (1 ≤ a ≤ b ≤ c ≤ 1000) — цена в бурлях за однократную покупку первого, второго и третьего тарифа аренды соответственно.
Вторая строка содержит целое число n (1 ≤ n ≤ 1015) — количество дней, в течение которых Роман планирует отдыхать во Флатландии и оставлять машину на охраняемой парковке.
Выведите единственное целое число — минимальное количество бурлей, которое Роману придётся потратить на аренду парковочного места.
4 7 20
10
14
2 9 38
36
47
В первом примере Роману выгодно взять 2 абонемента на неделю, это будет стоить 2·7 = 14 бурлей и позволит оплатить парковку на 14 дней.
Во втором примере выгодно купить 5 абонементов на неделю и 1 на день. Количество оплаченных дней будет ровно 36, а цена составит 1·2 + 5·9 + 0·38 = 47 бурлей.
