D. Hero of the Kingdom
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Hero of the Kingdom is a point-and-click adventure game, in which the protagonist sets off on a dangerous journey to save his/her father and becomes the hero of the kingdom.

Money in the game is called gold and can be used to buy various supplies or even complete certain quests. As the saying goes, one is never too rich to earn, our talented player BaoBao has just found a way to become rich. In the game, there is a mill where the owner sells flour for $$$p$$$ gold per bag. There is also a tavern where the barman buys flour at the price of $$$q$$$ gold per bag ($$$q \gt p$$$). It's obvious that BaoBao can pocket the difference, but moving between the two places and clicking on the buttons for buying and selling also takes time.

More precisely, if BaoBao buys $$$x$$$ bags of flour from the mill in one shot, he will have to spend $$$(ax + b)$$$ seconds and $$$px$$$ gold; If BaoBao sells $$$x$$$ bags of flour to the tavern in one shot, he will have to spend $$$(cx + d)$$$ seconds but then earn $$$qx$$$ gold. BaoBao currently has $$$m$$$ gold, but as it's time for him to go to bed, he can only play the game for at most $$$t$$$ seconds. Calculate the maximum number of gold he can have when he finishes playing the game.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 500$$$) indicating the number of test cases. For each test case:

The first line contains three integers $$$p$$$, $$$a$$$, and $$$b$$$ ($$$1 \le p, a \le 10^9$$$, $$$0 \le b \le 10^9$$$).

The second line contains three integers $$$q$$$, $$$c$$$, and $$$d$$$ ($$$p \lt q \le 10^9$$$, $$$1 \le c \le 10^9$$$, $$$0 \le d \le 10^9$$$).

The third line contains two integers $$$m$$$ and $$$t$$$ ($$$1 \le m, t \le 10^9$$$).

Output

For each test case, output one line containing one integer, indicating the maximum number of gold BaoBao can have after at most $$$t$$$ seconds.

Example
Input
3
5 2 3
8 1 5
14 36
5 2 0
8 1 3
17 6
100 1 0
10000 1 0
99 100000
Output
32
20
99
Note

For the first sample test case, one of the optimal strategy is:

  • BaoBao first buys $$$2$$$ bags of flour from the mill. It takes $$$2 \times 2 + 3 = 7$$$ seconds and costs $$$5 \times 2 = 10$$$ gold. Then he sells all flour to the tavern. It takes another $$$1 \times 2 + 5 = 7$$$ seconds but BaoBao earns $$$8 \times 2 = 16$$$ gold. BaoBao now has $$$14 - 10 + 16 = 20$$$ gold, and there are $$$36 - 7 - 7 = 22$$$ seconds remaining.
  • BaoBao then buys $$$4$$$ bags of flour from the mill. It takes $$$2 \times 4 + 3 = 11$$$ seconds and costs $$$5 \times 4 = 20$$$ gold. Then he sells all flour to the tavern. It takes another $$$1 \times 4 + 5 = 9$$$ seconds but BaoBao earns $$$8 \times 4 = 32$$$ gold. BaoBao now has $$$20 - 20 + 32 = 32$$$ gold, and there are $$$22 - 11 - 9 = 2$$$ seconds remaining.
  • Now BaoBao doesn't have time to buy or sell flour. So the answer is $$$32$$$.

For the second sample test case, BaoBao only has time to buy and sell one bag of flour. So the answer is $$$17 - 5 + 8 = 20$$$.

For the third sample test case, BaoBao doesn't have enough gold to buy flour. So the answer is $$$99$$$.