Kansainvälinen kapybaransilityskerho valmistelee T-paitoja tapahtumaa varten. Kokoja on neljä, S, M, L ja XL, kasvavassa järjestyksessä. Tarvittavien T-paitojen lukumäärät ovat vastaavasti $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ ja $n_{\mathrm{XL}}$. Vakiovärivoimakkuudella kokojen S, M, L ja XL T-paidat vaativat vastaavasti $B$, $Br$, $Br^2$ ja $Br^3$ yksikköä väriainetta.

Värjäyskone käyttää kokonaislukuvoimakkuutta $x$. Pienin sallittu värivoimakkuus on $P$, ja $x = K$ on vakiovoimakkuus. Näin ollen luvun $x$ on toteutettava ehto $P \le x \le K$. Jos T-paita vaatii vakiovoimakkuudella $q$ yksikköä, sen värjääminen voimakkuudella $x$ kuluttaa $\lceil qx/K \rceil$ yksikköä. Kaikkien T-paitojen on käytettävä samaa voimakkuutta $x$.

Kun käytettävissä on $A$ yksikköä väriainetta, etsi suurin mahdollinen voimakkuus $x$, jolla kaikki T-paidat voidaan värjätä käyttämättä enempää kuin $A$ yksikköä. Jos tällaista lukua $x$ ei ole olemassa, tulosta $-1$.

Syöte

Syöte sisältää $T$ testitapausta. Ensimmäisellä rivillä on kokonaisluku $T$ ($1 \le T \le 100$), testitapausten lukumäärä. Jokainen testitapaus koostuu yhdeksästä kokonaisluvusta, jotka annetaan seuraavassa muodossa:

$$ n_{\mathrm{S}} \ n_{\mathrm{M}} \ n_{\mathrm{L}} \ n_{\mathrm{XL}} \ r \ A \ B \ P \ K $$

$n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ ja $n_{\mathrm{XL}}$ tarkoittavat kokojen S, M, L ja XL T-paitojen lukumääriä vastaavasti ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ ja $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Arvo $r$ tarkoittaa kerrointa, jolla vakiovoimakkuudella tarvittavan väriaineen määrä kasvaa jokaisen kokoluokan kasvun myötä ($1 \le r \le 10$).

$A$ tarkoittaa käytettävissä olevan väriaineen kokonaismäärää yksikköinä ($0 \le A \le 10^{15}$).

$B$ tarkoittaa yhden S-kokoisen T-paidan värjäämiseen vakiovoimakkuudella tarvittavan väriaineen määrää yksikköinä ($1 \le B \le 10^6$).

$P$ tarkoittaa pienintä sallittua värivoimakkuutta ja $K$ tarkoittaa vakiovärivoimakkuutta ($1 \le P \le K \le 10^9$).

Tuloste

Tulosta jokaiselle testitapaukselle suurin sellainen kokonaisluku $x$, että $P \le x \le K$ ja kaikki T-paidat voidaan värjätä käyttäen enintään $A$ yksikköä väriainetta. Jos tällaista kokonaislukua ei ole olemassa, tulosta $-1$.

Esimerkit

Syöte 1

3
1 1 1 1 2 15 2 1 12
2 0 1 0 3 8 2 4 10
0 0 0 1 10 1000 1 900000 999999

Tuloste 1

6
-1
999999