F. Gold Cubes
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A company sells gold cubes, or at least that's what they call cubes filled with dirt that contain gold nuggets. To be precise, in the fine print, it specifies that each cube contains at least 100 milligrams of gold. Furthermore, they also claim that there is a possibility for the buyer to make money, as there are cubes that contain gold worth more than the price at which they are sold. The milligram of gold is valued at 5 cents, and the company sells its cubes at a price of $$$V$$$ euros.

The nuggets are categorized into 3 categories, each of which we assume has the same average weight:

  • Category 1: Nuggets of $$$A$$$ milligrams.
  • Category 2: Nuggets of $$$B$$$ milligrams.
  • Category 3: Nuggets of $$$C$$$ milligrams.

Calculate the maximum possible profit, in cents, that the company can achieve, respecting the following conditions:

  • Each cube contains at least 100 milligrams of gold.
  • There is at least one cube such that the value of the gold it contains exceeds the selling price of the cube.
  • You use at most $$$P_1$$$ nuggets from the first category, $$$P_2$$$ from the second, and $$$P_3$$$ from the third.

It is guaranteed that in the cases, a solution can always be found with a profit $$$\ge$$$ 0.

Input

The first line contains an integer $$$T$$$, indicating the number of cases.

For each case, the first line contains the integer $$$V$$$.

The second line contains the integers $$$A, B, C$$$.

The third line contains the integers $$$P_1, P_2, P_3$$$.

Output

Print for each case a line with the maximum possible profit in cents.

Scoring

$$$1 \le T \le 20$$$

$$$1 \le V \le 1000$$$

$$$1 \le A \lt B \lt C \le 100$$$

$$$1 \le P_1 + P_2 + P_3 \le 180$$$

17 points: $$$A = 1; \ B = 2; \ C = 50; \ P_1, P_3 \gt 0; \ P_2 = 0$$$

20 points: $$$A = 10; \ B = 20; \ C = 50$$$

21 points: $$$1 \le P_1 + P_2 + P_3 \le 15$$$

42 points: No additional restrictions.

Example
Input
2
9
10 20 30
30 0 0
10
1 2 25
1 0 12
Output
350
495