Найкраща назва

Обмеження: 2 сек., 256 МіБ

Богдан, Данило та Максим намагаються придумати назву для команди на одне цікаве змагання. За правилами змагань назва команди повинна складатися з малих латинських літер та мати довжину не більшу за \(n\). Оскільки хлопці не надто креативні, усі запропоновані ними варіанти були досить дивними та відразу відкидались. Тому вони попросили вас придумати для них назву.

Також відомо, що за кожне входження рядка bohdan у назву Богдан заплатить вам \(b\) гривень, за кожне входження рядка danylo Данило заплатить \(d\) гривень, а Максим заплатить вам \(m\) гривень за кожне входження рядка maksym.

Яку максимальну кількість грошей ви можете отримати, якщо придумаєте оптимальну назву для команди?

Вхідні дані

У єдиному рядку задано чотири цілі числа \(b\), \(d\), \(m\) та \(n\) — кількості гривень, які платитимуть вам Богдан, Данило й Максим відповідно, та довжину назви команди.

Вихідні дані

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

Обмеження

\(0 \le b, d, m \le 100\),

\(5\) тестів: \(1 \le n \le 100\),

\(5\) тестів: \(1 \le n \le 10^3\),

\(7\) тестів: \(1 \le n \le 10^6\),

\(8\) тестів: \(1 \le n \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 2 11	4

Примітки

У прикладі \(b = 2\), \(d = 1\), \(m = 2\) та \(n = 11\). Bи можете скласти назву maksymaksym та отримати від Максима 4 гривні (по дві за кожне входження).