Smartphone Game

Problem

Let's implement a function of a popular smartphone game. The game is based on the following specifications.

• 5 types of blocks are installed in 5 * 5 squares.
• Scores are set for each type of block.
• In addition to the block score, a bonus score is set for the score. The first bonus score is 1.
• You can arbitrarily decide only one block and move it up, down, left, and right up to n times. The destination block moves to the location where the source block was. In other words, the adjacent blocks will be exchanged.
• If blocks of the same type are lined up 3 or more vertically or 3 or more horizontally after moving, all the arranged blocks will disappear.
• After all the blocks that should disappear have disappeared, if there is no other block under one block, that block will fall. Falling means moving down until you reach one block above. If the block does not exist below, move to the bottom.
• Only 1 bonus score will be added after all blocks have fallen.
• If blocks are lined up after that, they will disappear and fall.
• When a block disappears, "block score * bonus score" will be added to your score for each block.

Find the maximum score you can get in one play.

Constraints

The input satisfies the following conditions.

• 0 ≤ n ≤ 5
• 1 ≤ aij ≤ 5
• 0 ≤ scorei ≤ 100
• The number of test cases does not exceed 10.
• All values ​​contained in the input are integers.

Input

The input consists of multiple datasets. Each dataset is represented below.

n a11 .. a15 .. .. a51 .. a55 score1 .. score5

aij is a number from 1 to 5 and represents the type of block. scorei represents the score for one block of the i-type. When n = -1, the input ends.

Output

Print the answer on one line for each dataset.

Example

Input

0 1 1 1 5 5 5 5 5 5 5 5 5 1 5 5 5 1 1 1 5 5 5 5 5 5 0 0 0 0 1 2 1 2 3 4 5 2 3 4 5 5 2 3 4 5 5 3 4 5 5 1 5 4 3 2 1 100 99 98 97 96 5 1 2 3 4 5 2 3 4 5 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 99 79 31 23 56 -1

Output

17 2040 926

inputFormat

input satisfies the following conditions.

• 0 ≤ n ≤ 5
• 1 ≤ aij ≤ 5
• 0 ≤ scorei ≤ 100
• The number of test cases does not exceed 10.
• All values ​​contained in the input are integers.

Input

The input consists of multiple datasets. Each dataset is represented below.

n a11 .. a15 .. .. a51 .. a55 score1 .. score5

aij is a number from 1 to 5 and represents the type of block. scorei represents the score for one block of the i-type. When n = -1, the input ends.

outputFormat

Output

Print the answer on one line for each dataset.

Example

Input

0 1 1 1 5 5 5 5 5 5 5 5 5 1 5 5 5 1 1 1 5 5 5 5 5 5 0 0 0 0 1 2 1 2 3 4 5 2 3 4 5 5 2 3 4 5 5 3 4 5 5 1 5 4 3 2 1 100 99 98 97 96 5 1 2 3 4 5 2 3 4 5 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 99 79 31 23 56 -1

Output

17 2040 926

样例

0
1 1 1 5 5
5 5 5 5 5
5 5 1 5 5
5 1 1 1 5
5 5 5 5 5
0 0 0 0 1
2
1 2 3 4 5
2 3 4 5 5
2 3 4 5 5
3 4 5 5 1
5 4 3 2 1
100 99 98 97 96
5
1 2 3 4 5
2 3 4 5 1
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
99 79 31 23 56
-1

17
2040
926

</p>