Bob is stuck in a cave represented by a matrix of rows and columns, where rows are numbered from to from top to buttom, and columns are numbered from to from left to right. The cell at the i-th row and the j-th column is denoted by .

Bob is currently at the cell , and the exit of the save is located at the cell .

Each cell in this cave contains a number, which is called the magic value. The magic value of cell is .

When Bob moves from one cell to an unvisited cell, he gains energy points equals to the product of two magic values. It means, if Bob moves from cell to cell , and cell (x, y) is unvisited, he will gain energy points.

Bob can move between cells that share an edge (not just a corner). On the exit cell, Bob can choose not to exit the cave and continue to explore the cave if he want to. Can you help him find the maximum number of energy points he can gain when he exits the cave.

输入描述:

The first line of the input gives the numbers of test cases, .  test cases follow.
Each test case contains two lines.
The first line contains six integers , , , ,  and  as described above. 
The next line contains fix integers in the following format, respectively:
     
These values are used to generate  as follows:
We define:
, for i = 3 to .
We also define:
, for  to , and  to .
.
.
.
.
.
.

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the maximum energy points that Bob can gain.

2
1 4 1 2 1 3
1 2 2 3 1 5
6 1 2 1 4 1
0 1 2 3 0 4

Case #1: 17
Case #2: 8

备注:

In Sample Case \#1, The matrix is:

one way to get 17 energy points is:
(1, 2)  (1, 1), get  energy points.
(1, 1)  (1, 2), get 0 energy points.
(1, 2)  (1, 3), get  energy points.
(1, 3)  (1, 4), get  energy points.
(1, 4)  (1, 3), get 0 energy points.
In Sample Case \#2, The matrix is:

one way to get 8 energy points is:
(2, 1)  (3, 1), get  energy points.
(3, 1)  (4, 1), get  energy points.