E. The Chariot
time limit per test
2.1 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the ever-changing and chaotic environment of Night City, uncertainty is the only certainty. For safe travel, edgerunners rely on the best technology. Despite their premium price and corporation background, Delamain AI armed cabs provide the most reliable mode of transportation.

Today, you need to make a lengthy journey across Night City. The Delamain cab's fare structure is as follows:

  • The base fare is $$$ A $$$ eurodollars, covering the first $$$ X $$$ meters.
  • For the next $$$ Y $$$ meters, the fare is $$$ B $$$ eurodollars per meter.
  • Beyond $$$ X + Y $$$ meters, the fare is $$$ C $$$ eurodollars per meter.

At any point, you may perform the following operation: stop and re-hail a cab. By doing so, you will immediately settle the cost of your previous cab, and the fare for the next one will be recalculated starting from the base fare. This operation can be performed for any number of times.

Now, you want to determine the minimum cost in eurodollars for traveling $$$D$$$ meters using Delamain cabs.

Input

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 2077$$$) — the number of test cases. The description of the test cases follows.

The input contains six integers in a line: $$$ A, B, C, X, Y, D ~ (0 \lt A, B, C, X, Y, D \lt 10 ^ {2077})$$$ in decimal representation, without leading zeros.

It is guaranteed that the sum of the number of digits of $$$A$$$ among $$$T$$$ test cases does not exceed $$$\texttt{0x2077}$$$. This constraint also applies individually to $$$B, C, X, Y, D$$$.

The value $$$\texttt{0x2077}$$$ used in the constraint is a hexadecimal number, equal to the decimal number $$$8311$$$.

Output

For each test case, output a single line containing the minimized cost in eurodollars for traveling $$$D$$$ meters using Delamain's cabs.

It can be proven that the answer is a positive integer. Please print the integer in decimal form without leading zeros.

Example
Input
5
160 27 41 3 12 3
160 27 41 3 12 4
160 27 41 3 12 99
1 999 999 1 99 999
999 999 1 1 99 9999999999999999
Output
160
187
3226
999
10000000000099799
Note

For the fourth sample, the optimal solution is to hail $$$999$$$ cabs, hailing a new one every meter. It seems quite weird, but you are confident that this is the optimal way to live the life in Night City.