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)\)