크러시 피버

게임이라면 플랫폼을 가리지 않는 준서가 모바일 앱 스토어에서 Crush Fever라는 게임을 찾았다. 유닛을 키워 파티를 짜고 던전을 도는 게임인데, 전투는 퍼즐로 진행한다. 손으로는 던전이 도무지 깨지지 않자 준서는 게임을 자동으로 돌리는 프로그램을 만들기로 했다. 화면을 대신 눌러 주는 부분은 직접 만들고, 퍼즐에서 높은 점수를 내는 부분을 당신에게 맡겼다.

퍼즐 조각은 5종류이고, 위 그림처럼 어지럽게 흩어져 있지 않고 격자 위에 가지런히 놓여 있다. 자기 차례가 오면 조각을 세 번 누른다. 조각을 한 번 누르면 그 조각이 파괴되고, 파괴된 조각과 상하좌우로 이어진 같은 종류의 조각도 함께 파괴된다. 연결을 따라 연쇄로 파괴되므로 한 번 누를 때마다 같은 종류로 연결된 덩어리 하나가 통째로 사라진다. 한 번에 $P$개가 파괴되면 $P^2$점을 얻는다. 그 다음 공중에 뜬 조각이 같은 열을 따라 아래로 가라앉아 빈칸을 메운다.

예를 들어 다음 퍼즐에서 노랗게 칠한 3 덩어리의 조각 하나를 누르면

아래와 같은 모습이 된다.

준서가 한 차례에 얻을 수 있는 점수의 최댓값을 구하라. 격자가 비면 남은 횟수는 누를 수 없다.

입력은 표준 입력으로 받는다. 첫 줄에 퍼즐의 너비 $M$과 높이 $N$이 공백으로 구분되어 주어진다. ($1 \le M, N \le 8$)

둘째 줄부터 $N$개의 줄에 각 행의 조각 종류 $c$가 $M$개씩 공백으로 구분되어 주어진다. ($1 \le c \le 5$) 이 중 첫 줄이 격자의 맨 위 행이고 마지막 줄이 바닥 행이다. 처음에는 모든 칸에 조각이 하나씩 있다.

출력은 표준 출력으로 한다. 준서가 한 차례에 얻을 수 있는 최대 점수를 한 줄에 출력한다.