Jawbreak

Jawbreaker is a simple game that used to come with PDAs and mobile phones. The game starts with a board full of coloured balls. The player picks a group of same-coloured balls that holds at least 3 balls, and the whole group disappears at once. A group here means every same-coloured ball connected to the picked one, so the player cannot remove only part of a group.

When balls disappear, the balls above them in the same column fall down, and empty space is left at the top of the column. If a column becomes completely empty, every column to its right shifts left, and empty space is left on the right side of the board.

The score starts at 0. Each move adds the square of the number of removed balls to the score. Removing every ball from the board wins the game and adds a bonus of 1000 points. The game is over when no group of 3 or more balls remains.

Two balls are neighbours when they touch above, below, to the left, or to the right. Balls that touch only diagonally are not neighbours.

You are given an $n \times n$ board with $m$ colours. Write a program that finds the maximum score reachable from that board.

The first line has the board size $n$ and the number of colours $m$. ($1 \le n \le 8$, $1 \le m \le 4$)

Each of the next $n$ lines has $n$ characters describing the initial board. Each character is a digit between $1$ and $m$ and gives the colour of the ball on that square.

Print the maximum score reachable from the initial board.