You are given $n$ problems. The problems are of three types, 'Type1', 'Type2', and 'Type3'. There are $t1$ 'Type1' problems, $t2$ 'Type2' problems, and $t3$ 'Type3' problems. You can solve each problem using any of the three methods, 'A', 'B', and 'C'. You can use a particular method only a limited number of times that is, method 'A' for $a$ times, method 'B' for $b$ times, and method 'C' for $c$ times. 

You are given a $3\times 3$ matrix $A$ where $A[i][j]$ represents the effort to solve a Type $i$ problem using Method $j$. You are required to find the minimum effort required to solve all the problems.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $n$ denoting the number of problems.
• The second line of each test case contains three space-separated integers denoting the values of $t1$, $t2$, and $t3$ respectively.
• The third line of each test case contains three space-separated integers denoting the values of $a$, $b$, and $c$ respectively.
• Next three lines of each test case contain three space-separated integers of matrix $A$.

Output format

For each test case, print the minimum effort required to solve all the problems in a new line.

Constraints

$1 \le T \le 5\\ 1 \le n \le 1e9$

$0 \le t1,\ t2,\ t3 \le 1e9$ (sum of $t1$, $t2$, and $t3$ is equal to $n$)

$0 \le a,\ b,\ c \le 1e9$ (sum of $a$, $b$, and $c$ is equal to $n$)

$1 \le A[i][j] \le 1e9\ (1 \le i,\ j \le 3)$