Problem E
Trädkojebygge

Eftersom att det börjar bli varmt ute vill Mona bygga en koja, och hon har hittat en massa brädor som hon kan använda. Hon har delat in dem i tre olika kategorier ($a$,$b$ och $c$) efter hur stabila de är att bygga med. Närmare bestämt så har sort $a$ ett stabilitetsvärde av $1$, sort $b$ har ett stabilitetsvärde av $2$ och sort $c$ har ett stabilitetsvärde av $3$. För att en våning i kojan ska vara stabil måste alla plankor som används till den sammanlagt ha en viss stabilitet $k$. Hon har inga problem med att använda olika många plankor för olika våningar. Såklart vill Mona bygga en så hög koja som möjligt så att den är riktigt ståtlig. Givet hur många plankor hon har av varje sort, hur många våningar kan Mona maximalt bygga?

Indata

Första raden innehåller fyra heltal $a$, $b$, $c$ och $k$, hur många plankor det finns av varje sort och hur hög stabilitet varje våning måste ha för att vara stabil.

Utdata

Skriv ut ett tal, det maximala antalet våningar som Mona kan bygga.

Poängsättning

Din lösning kommer att testas på fem olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen. För alla testgrupper gäller förutom kraven nedan även $0 \leq a, b, c \leq 1000$, $a \cdot b \cdot c \leq 10^7$ och $1 \leq k \leq 10000$.

Förklaring

I det första exempelfallet kan Mona bygga tre våningar genom att först använda en planka vardera av $a$ och $c$ till de två första våningarna och sedan använda två plankor av $b$ till den sista våningen. I det andra exempelfallet kan Mona bygga två våningar genom att använda två plankor av $c$ till vardera våning. I det tredje exempelfallet kan Mona bygga tre våningar genom att till de två första våningarna använda två plankor av $b$ och en planka av $c$, och till den sista våningen använda en planka av $a$ och två plankor av $c$.

2 2 2 4

3

0 0 4 4

2

1 4 4 7

3