Jawbreaker is a simple game that is often bundled with PDAs and handphones. A player starts with a board filled with coloured balls. The player can select any group of 3 or more adjacent, like-coloured balls to make them disappear. When the selected balls
are removed, balls in the same column(s) above the removed balls fall down, leaving empty space at the top. If any columns become empty as a result of this, the remaining columns to the right of the empty columns are compacted to the left, leaving empty
space on the right of the board.
A player start with a score of 0. Each move adds to the player's score by the square of the number of balls removed. A player wins Jawbreaker if he/she is able to remove all balls from the board. A win adds a bonus of 1,000 points to the score. The game is
over if there are no valid moves remaining on the board.
Adjacent means balls directly above, below or to the left or right. Diagonally touching balls are considered not adjacent.
In this problem, you are given a n x n Jawbreaker board with m colours. Your program should output the maximum score that can be achieved given the board.
Input
The first input line gives the size of the board
n and the number of colours
m, where (1 ≤
n ≤ 8 and 1 ≤
m ≤ 4). The remaining
n lines give the initial board, where each of
n characters in the line is a number 1 to
m, indicating its colour.
Output
Output the maximum score that can be achieved from the initial board.
Sample Input 1
3 3
113
211
112
Sample Output 1
36
Explanation for Sample Output 1
For Example 1, there is only one valid move to remove the group of six 1s, which results in the following board ('-' indicate empty spaces). Note that after the removal of the group of 1s, the second column is empty and is compacted.
---
-3-
22-
No subsequent moves are possible.
Sample Input 2
4 3
3222
3211
2212
3322
Sample Output 2
1106
Explanation for Sample Output 2
For Example 2, there are three possible initial moves. Only the removal of the group of three 1s allows the two groups of 2s to collapse into one large group that will result in the maximum score.