Problem D: Smartphone Game
Problem
人気のスマフォゲームの一機能を実装してみよう。ゲームは以下の仕様に基づく。
- 5*5のマスに、5種類のブロックが設置されている。
- それぞれの種類のブロックには得点が設定されている。
- 得点には、ブロックの得点の他に、ボーナス得点が設定されている。最初のボーナス得点は1である。
- ブロックを任意に1つだけ決めて、最大でn回まで上下左右に移動できる。移動先のブロックは移動元のブロックのあった場所に移動する。つまり、隣接したブロックを交換する事になる。
- 移動した後、同じ種類のブロックが縦3個以上又は横3個以上に並んだ場合、並んだブロックは全て消える。
- 消えるべきブロックが全て消えた後、あるブロックの下に別のブロックが存在しない場合、そのブロックは落下する。落下とは、あるブロックの1つ上に辿り着くまで下に移動する事をいう。ブロックが下に存在しない場合は一番下に移動する。
- 全てのブロックの落下後にボーナス得点が1だけ加算される。
- その後にブロックが並んだ場合、さらに消え、落下する。
- ブロックが消える時に、ブロック1つにつき「ブロックの得点*ボーナス得点」が自分の得点に加算される。
1回のプレイで得られる最大の点数を求めよ。
Input
入力は複数のデータセットからなる。
各データセットは以下で表される。
n
a11 .. a15
.
.
a51 .. a55
score1 .. score5
aijは1から5までの数字で、ブロックの種類を表す。
scoreiはi種類目のブロック1つ分の得点を表す。
n = -1 の時、入力が終了する。
Constraints
入力は以下の条件を満たす。
- 0 ≤ n ≤ 5
- 1 ≤ aij ≤ 5
- 0 ≤ scorei ≤ 100
- テストケースの数は 10 を超えない。
- 入力に含まれる値は全て整数である。
Output
各データセット毎に、答えを一行に出力しなさい。
Sample 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
Sample Output
17
2040
926