Alþjóðlegi flóðsvínaklappklúbburinn er að undirbúa stuttermaboli fyrir viðburð. Það eru fjórar stærðir, S, M, L og XL, í vaxandi röð. Fjöldi stuttermabola sem þarf af hverri stærð er $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ og $n_{\mathrm{XL}}$, í þessari röð. Við staðlaðan litstyrk þurfa stuttermabolir í stærðum S, M, L og XL $B$, $Br$, $Br^2$ og $Br^3$ einingar af litarefni, í þessari röð.

Litunarvélin notar heiltölustyrk $x$. Lágmarkslitstyrkur sem leyfður er nemur $P$, og $x = K$ er staðalstyrkurinn. Því verður $x$ að uppfylla $P \le x \le K$. Ef stuttermabolur þarf $q$ einingar við staðalstyrk, þá notar litun hans við styrk $x$ alls $\lceil qx/K \rceil$ einingar. Allir stuttermabolir verða að nota sama styrkinn $x$.

Gefið að til séu $A$ einingar af litarefni, finndu mesta mögulega styrkinn $x$ þannig að hægt sé að lita alla stuttermabolina án þess að nota meira en $A$ einingar. Ef ekkert slíkt $x$ er til, skrifaðu út $-1$.

Inntak

Inntakið inniheldur $T$ prófunartilvik. Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 100$), fjölda prófunartilvika. Hvert prófunartilvik samanstendur af níu heiltölum sem gefnar eru á eftirfarandi sniði:

$$ 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}}$ og $n_{\mathrm{XL}}$ tákna fjölda stuttermabola í stærðum S, M, L og XL, í þessari röð ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ og $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Gildið $r$ táknar stuðulinn sem magn litarefnis við staðalstyrk margfaldast með við hverja stærðaraukningu ($1 \le r \le 10$).

$A$ táknar heildarmagn litarefnis sem er í boði, í einingum ($0 \le A \le 10^{15}$).

$B$ táknar magn litarefnis sem þarf til að lita einn stuttermabol í stærð S við staðalstyrk, í einingum ($1 \le B \le 10^6$).

$P$ táknar lágmarkslitstyrk sem leyfður er, og $K$ táknar staðlaðan litstyrk ($1 \le P \le K \le 10^9$).

Úttak

Fyrir hvert prófunartilvik skal skrifa út stærstu heiltöluna $x$ þannig að $P \le x \le K$ og hægt sé að lita alla stuttermabolina með því að nota í mesta lagi $A$ einingar af litarefni. Ef engin slík heiltala er til, skrifaðu út $-1$.

Dæmi

Inntak 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

Úttak 1

6
-1
999999