시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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 × n Jawbreaker board with m colours. Your program should output the maximum score that can be achieved given the board.

입력

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 the maximum score that can be achieved from the initial board.

예제 입력 1

3 3
113
211
112

예제 출력 1

36

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-

예제 입력 2

4 3
3222
3211
2212
3322

예제 출력 2

1106

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.