Best Name

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Bohdan, Danylo and Maksym are trying to come up with a team name for an interesting competition. According to the rules of the competition, the team name must consist of lowercase Latin letters and have a length of at most \(n\). Since the guys are not very creative, all the options they suggested were quite strange and immediately discarded. Therefore, they asked you to come up with a name for them.

It is also known that for each occurrence of the string bohdan in the name, Bohdan will pay you \(b\) hryvnias, for each occurrence of the string danylo, Danylo will pay \(d\) hryvnias, and Maksym will pay you \(m\) hryvnias for each occurrence of the string maksym.

What is the maximum amount of money you can get if you come up with an optimal team name?

Input

The single line contains four integers \(b\), \(d\), \(m\) and \(n\) — the amounts of hryvnias that Bohdan, Danylo, and Maksym will pay you respectively, and the length of the team name.

Output

Print a single integer in one line — the answer to the problem.

Constraints

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

\(5\) tests: \(1 \le n \le 100\),

\(5\) tests: \(1 \le n \le 10^3\),

\(7\) tests: \(1 \le n \le 10^6\),

\(8\) tests: \(1 \le n \le 10^9\).

Samples

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

Notes

In the example, \(b = 2\), \(d = 1\), \(m = 2\) and \(n = 11\). You can construct the name maksymaksym and get 4 hryvnias from Maksym (two for each occurrence).