Jawbreak

Jawbreaker는 PDA와 휴대폰에 기본으로 들어 있던 간단한 게임이다. 게임을 시작하면 게임판이 색깔 공으로 가득 차 있다. 플레이어는 같은 색 공이 상하좌우로 이어진 덩어리 중에서 공이 3개 이상인 덩어리를 하나 골라 없앨 수 있다. 여기서 덩어리는 서로 이어진 같은 색 공 전체를 뜻한다. 덩어리를 고르면 그 공이 한꺼번에 사라지며, 덩어리의 일부만 골라서 없앨 수는 없다.

공이 사라지면 같은 열에서 그 위에 있던 공이 아래로 떨어지고, 열 위쪽에 빈 자리가 생긴다. 이때 어떤 열이 통째로 비면 그 오른쪽에 있던 열이 모두 왼쪽으로 당겨지고, 게임판 오른쪽에 빈 자리가 남는다.

점수는 0에서 시작한다. 한 번 없앨 때마다 없앤 공 개수의 제곱이 점수에 더해진다. 게임판의 공을 모두 없애면 이기고, 보너스로 1000점을 더 받는다. 없앨 수 있는 덩어리가 하나도 남지 않으면 게임이 끝난다.

이웃한 공은 위, 아래, 왼쪽, 오른쪽으로 맞닿은 공이다. 대각선으로만 닿은 공은 이웃이 아니다.

색깔이 $m$가지인 $n \times n$ 게임판이 주어진다. 이 게임판에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 게임판의 크기 $n$과 색깔의 수 $m$이 주어진다. ($1 \le n \le 8$, $1 \le m \le 4$)

다음 $n$개 줄에 게임판의 처음 상태가 주어진다. 각 줄은 $n$개의 문자로 이루어지고, 각 문자는 $1$ 이상 $m$ 이하의 숫자로 그 자리에 놓인 공의 색을 나타낸다.

처음 게임판에서 얻을 수 있는 최대 점수를 출력한다.