Халықаралық капибара сипау клубы іс-шараға арнап футболкалар дайындап жатыр. Өсу ретімен S, M, L және XL деген төрт өлшем бар. Қажетті футболкалар саны сәйкесінше $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ және $n_{\mathrm{XL}}$. Стандартты түс қанықтылығында S, M, L және XL өлшемді футболкалар сәйкесінше $B$, $Br$, $Br^2$ және $Br^3$ бірлік бояуды қажет етеді.

Бояу машинасы бүтін $x$ қанықтылығын пайдаланады. Рұқсат етілген ең төменгі түс қанықтылығы — $P$, ал $x = K$ — стандартты қанықтылық. Демек, $x$ саны $P \le x \le K$ шартын қанағаттандыруы тиіс. Егер футболкаға стандартты қанықтылықта $q$ бірлік бояу қажет болса, оны $x$ қанықтылығымен бояу үшін $\lceil qx/K \rceil$ бірлік бояу жұмсалады. Барлық футболкалар бірдей $x$ қанықтылығымен боялуы тиіс.

$A$ бірлік бояу берілген. Барлық футболкаларды $A$ бірліктен артық бояу жұмсамай бояп шығуға болатын ең үлкен мүмкін $x$ қанықтылығын табыңыз. Егер ондай $x$ табылмаса, $-1$ шығарыңыз.

Кіріс деректер

Кіріс деректер $T$ тест жиынтығынан тұрады. Бірінші жолда тест жиынтықтарының санын білдіретін бүтін $T$ саны ($1 \le T \le 100$) берілген. Әрбір тест жиынтығы келесі форматта берілген тоғыз бүтін саннан тұрады:

$$ 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}}$ және $n_{\mathrm{XL}}$ сәйкесінше S, M, L және XL өлшемді футболкалардың санын білдіреді ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ және $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

$r$ мәні өлшем әр сатыға үлкейген сайын стандартты қанықтылықта қажет болатын бояу мөлшерінің неше есе артатынын көрсетеді ($1 \le r \le 10$).

$A$ қолжетімді бояудың жалпы мөлшерін бірлікпен білдіреді ($0 \le A \le 10^{15}$).

$B$ стандартты қанықтылықта S өлшемді бір футболканы бояуға қажетті бояу мөлшерін бірлікпен білдіреді ($1 \le B \le 10^6$).

$P$ рұқсат етілген ең төменгі түс қанықтылығын, ал $K$ стандартты түс қанықтылығын білдіреді ($1 \le P \le K \le 10^9$).

Шығыс деректер

Әрбір тест жиынтығы үшін $P \le x \le K$ шарты орындалатын және барлық футболкаларды ең көбі $A$ бірлік бояу жұмсап бояуға болатын ең үлкен бүтін $x$ санын шығарыңыз. Егер ондай бүтін сан болмаса, $-1$ шығарыңыз.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

6
-1
999999