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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

Output

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

Constraints

$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$.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 1 2 11	4

Notes

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