Problem A
RGB Hydra

Den här skräckinjagande varelsen kan ha huvuden av tre olika färger. Från början har Hydran

• $R$ röda huvuden,

• $G$ gröna huvuden, och

• $B$ blåa huvuden.

Varje gång jägaren hugger av ett huvud av en viss färg från Hydran, växer det genast ut två nya huvuden - ett av varje av de andra två färgerna. Till exempel, om jägaren hugger av ett rött huvud, växer det ut ett grönt och ett blått huvud genast.

Jägaren, driven av sitt mod och sin ambition, vill inte bara besegra Hydran utan också lämna ett bestående spår av sin resa. För att göra det vill jägaren att så mycket rött som möjligt ska synas på Hydran - målet är att maximera antalet röda huvuden!

Innan Hydran går till anfall hinner jägaren utföra som mest $k$ drag, där varje drag innebär att ett enda huvud huggs av.

Vad är det maximala antalet röda huvuden som Hydran kan ha efter högst $k$ drag?

Indata

Indatan består av en rad med 4 heltal $R$, $G$, $B$, och $k$ ($0\le R,G,B,k\le {10}^{18}$), där:

• $R$ är antalet röda huvuden,

• $G$ är antalet gröna huvuden,

• $B$ är antalet blåa huvuden,

• $k$ är det maximala antalet drag jägaren hinner utföra.

Det är garanterat att Hydran har åtminstone ett huvud från början, det vill säga att $R+G+B\ge 1$.

(Notera även att talen $R,G,B,k$ är väldigt stora, och i t.ex. C++ kommer det behövas användas long long istället för int.)

Utdata

Skriv ut ett heltal: det maximala antalet röda huvuden som Hydran kan ha efter högst $k$ drag.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I det första exempelfallet har Hydran endast $1$ blått huvud, och jägaren hinner göra max $1$ drag. Det enda draget som kan göras är att hugga av det blåa huvudet, vilket resulterar i att Hydran har $1$ rött huvud och $1$ grönt huvud. Inga fler drag kan utföras, vilket innebär att $1$ rött huvud är det maximala antalet.

I det andra exempelfallet har Hydran $4$ röda huvuden, $3$ gröna huvuden och $2$ blåa huvuden, och jägaren hinner göra max $1$ drag. Jägaren kan till exempel välja att hugga av ett grönt huvud, vilket resulterar i att Hydran har $5$ röda huvuden, $2$ gröna huvuden och $3$ blåa huvuden. Efter det draget kan inga fler drag utföras. Det finns inget sätt att få fler än $5$ röda huvuden, vilket innebär att $5$ är svaret.

I det tredje exempelfallet har Hydran $10$ huvuden av vardera färg. Eftersom jägaren inte hinner göra några drag alls (då $k=0$), förblir antalet röda huvuden $10$.

0 0 1 1

1

4 3 2 1

5

10 10 10 0

10

926332030620250124 57836736120250125 503852839920250126 804672315982687419

1731004346602937543