시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB61116.667%

문제

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.

예제 입력 1

2
1 1 4 5 1 4
2 5 1 9 9 6

예제 출력 1

4
25