P17534 [JAG 2026 Summer Camp #1] Capybara Petting Club

The International Capybara Petting Club is preparing T-shirts for an event. There are four sizes, S, M, L, and XL, in increasing order. The numbers of T-shirts needed are $n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}}$, and $n_{\mathrm{XL}}$, respectively. At the standard color intensity, T-shirts of sizes S, M, L, and XL require $B,Br,Br^2$, and $Br^3$ units of dye, respectively. The dyeing machine uses an integer intensity $x$. The minimum allowed color intensity is $P$, and $x=K$ is the standard intensity. Thus, $x$ must satisfy $P\le x\le K$. If a T-shirt requires $q$ units at the standard intensity, dyeing it at intensity $x$ uses $\lceil qx/K\rceil$ units. All T-shirts must use the same intensity $x$. Given $A$ units of dye, find the maximum possible intensity $x$ such that all T-shirts can be dyed without using more than $A$ units. If no such $x$ exists, output `-1`.

The input contains $T$ test cases. The first line contains an integer $T$ ($1\le T\le 100$), the number of test cases. Each test case consists of nine integers given in the following format: ```text n_S n_M n_L n_XL r A B P K ``` $n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}}$, and $n_{\mathrm{XL}}$ denote the numbers of T-shirts of sizes S, M, L, and XL, respectively ($0\le n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}},n_{\mathrm{XL}}\le 10^5$ and $n_{\mathrm{S}}+n_{\mathrm{M}}+n_{\mathrm{L}}+n_{\mathrm{XL}}\ge 1$). The value $r$ denotes the factor by which the amount of dye required at the standard intensity increases with each increase in size ($1\le r\le 10$). $A$ denotes the total amount of dye available, in units ($0\le A\le 10^{15}$). $B$ denotes the amount of dye required to dye one size-S T-shirt at the standard intensity, in units ($1\le B\le 10^6$). $P$ denotes the minimum allowed color intensity, and $K$ denotes the standard color intensity ($1\le P\le K\le 10^9$).

For each test case, output the maximum integer $x$ such that $P\le x\le K$ and all T-shirts can be dyed using at most $A$ units of dye. If no such integer exists, output `-1`.