23149번 - Might and Magic 다국어

문제

Two heroes are fighting, whose names are hero 0ドル$ and hero 1ドル$ respectively.

You are controlling the hero 0ドル,ドル and your enemy is the hero 1ドル$. Each hero has five integer attributes: ATTACK, DEFENSE, POWER, KNOWLEDGE, and HEALTH. When two heroes battle with each other, they will take turns to attack, and your hero moves first. One hero can make $exactly one attack$ in one turn, either a physical attack or a magical attack.

Assume their attributes are $A_i,ドル $D_i,ドル $P_i,ドル $K_i,ドル $H_i$ (0ドル \leq i \leq 1)$. For hero $i,ドル its physical attack's damage is $C_p \cdot \max (1, A_i - D_{1-i}),ドル while its magical attack's damage is $C_m \cdot P_i$. Here, $C_p$ and $C_m$ are given constants.

After hero $i$'s attack, $H_{1-i}$ will decrease by the damage of its enemy. If $H_{1-i}$ is lower or equal to 0ドル,ドル the hero $(1-i)$ loses, the hero $i$ wins, and the battle ends.

Hero $i$ can make magical attacks no more than $K_i$ times in the whole battle.

Now you know your enemy is a Yog who is utterly ignorant of magic, which means $P_1 = K_1 = 0,ドル and he will only make physical attacks. You can distribute $N$ attribute points into four attributes $A_0,ドル $D_0,ドル $P_0,ドル $K_0$ arbitrarily, which means these attributes can be any non-negative integers satisfying 0ドル \leq A_0 + D_0 + P_0 + K_0 \leq N$.

Given $C_p,ドル $C_m,ドル $H_0,ドル $A_1,ドル $D_1,ドル and $N,ドル please calculate the maximum $H_1$ such that you can build hero 0ドル$ and fight so that it wins the game.

입력

The first line contains an integer $T$ (1ドル \leq T \leq 10^4$), the number of test cases. Then $T$ test cases follow.

The first and only line of each test case contains six integers $C_p,ドル $C_m,ドル $H_0,ドル $A_1,ドル $D_1,ドル $N$ (1ドル \leq C_p, C_m, H_0, A_1, D_1, N \leq 10^6$), the attributes described above.

출력

For each test case, print a line with one integer: the maximum enemy health such that it is possible to win.

제한

힌트