Problem J
Coin Exchange

Lorenzo of Valtier is a traveling merchant navigating the fractured realms of the Five Kingdoms. Each nation mints its own unique coins using secretive forging techniques, creating a hidden economy of conversions:

Currencies

• Aetherspire Dominion: Obsidian discs etched with celestial runes (Aetherspire Coin)

• Bleakmarch Protectorate: Bone-white tetrahedrons that scream when heated (Bleakmarch Coin)

• Crimson Falconate: Blood-veined square that warm before storms (Crimson Coin)

• Drowned King’s Reach: Barnacle-encrusted hexagons that smell of brine (Drowned Coin)

• Emberveil Syndicate: Geometric amber prisms containing frozen flames (Emberveil Coin)

Exchange Rates (Black Market, One-way Currency Exchange):

• $3$ Aetherspire $\rightarrow $ $1$ Bleakmarch ("Three stars bow to the Pale Lord")

• $3$ Bleakmarch $\rightarrow $ $1$ Crimson ("The Bloodied Falcon’s Toll")

• $5$ Aetherspire $\rightarrow $ $1$ Crimson ("Stardust to Blood" smuggling route)

• $3$ Emberveil $\rightarrow $ $2$ Drowned ("Fire drowns in black waters")

• $3$ Bleakmarch $\rightarrow $ $4$ Emberveil ("Bleaching the Pale Mark")

Forbidden Technique: The Argentum Revenant Tome allows you to exchange $2$ Drowned $\rightarrow $ $3$ Bleakmarch ("Raising Drowned Silver") for a maximum of $X$ uses, after which the Pale Inquisition is triggered.

Given Lorenzo of Valtier’s initial coin stash and a limit of $X$ on the number of times the forbidden technique may be used, your goal is to maximize the number of Crimson Falconate coins that can be obtained using a series of exchanges. Solving this puzzle may unlock the secret behind how Lorenzo of Valtier became wealthy!

Figure 1: Echange Rates. (Coin images created by DALL·E-3)

Input

A line containing six integers: $A$ (Aetherspire Coin), $B$ (Bleakmarch Coin), $C$ (Crimson Coin), $D$ (Drowned Coin), $E$ (Emberveil Coin), $X$ (maximum use of the Forbidden Technique) satisfying $0 \leq A, B, C, D, E, X \leq 10^9$.

Output

A single integer indicating the number of maximum possible Crimson Coins that can be obtained using a series of zero or more of exchanges.

Explanation of First Sample Case

Lorenzo of Valtier can obtain $7$ Crimson coins using the following sequence of exchanges beginning with the initial coin count of $(A,B,C,D,E) = (1,2,3,4,5)$

• $3$ Emberveil coins are converted to $2$ Drowned coins. The coin count is now $(1,2,3,6,2)$.

• Using the forbidden exchange three times, $6$ Drowned coins are converted to $9$ Bleakmarch coins. The coin count is now $(1,11,3,0,2)$.

• $6$ Bleakmarch coins are converted to $8$ Emberveil coins. The coin count is now $(1,5,3,0,10)$.

• $9$ Emberveil coins are converted to $6$ Drowned coins. The coin count is now $(1,5,3,6,1)$.

• Using the forbidden exchange three more times, $6$ Drowned coins are converted to $9$ Bleakmarch coins. The coin count is now $(1,14,3,0,1)$.

• Finally, $12$ Bleakmarch coins are converted to $4$ Crimson coins. The final coin count is now $(1,2,7,0,1)$.

Note that the forbidden exchange was not used more than $X = 6$ times.

1 2 3 4 5 6

7

5 5 5 5 5 5

11

1000000000 0 500000000 123 456789 1000000000

950114243