타일은 형형색색
시간 제한2초메모리 제한512 MB
M×N 격자에서 각 글자는 정확히 두 번 나타난다. 빈 칸을 누르면 상하좌우로 처음 보이는 타일 중 같은 색끼리 사라지며, 제거할 수 있는 타일 수의 최댓값을 구한다.
문제
ICPC에서 좋은 성적을 내려면 수행이 필수적이다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수행을 하기로 했다.
오늘의 수행은 유행하는 퍼즐을 빠르게 풀어 순발력을 기르는 것이다. 오늘 도전하는 것은 색색의 타일이 늘어서 있고 그것들을 잘 지워 나가는 퍼즐이다.
초기 상태에서는 그리드의 몇몇 칸에 타일이 놓여 있다. 각 타일에는 색이 있다. 플레이어는 게임 시작 후 다음 절차로 주어지는 조작을 여러 번 할 수 있다.
- 타일이 놓여 있지 않은 칸 하나를 선택하고, 그 칸을 두드린다.
- 두드린 칸에서 위쪽으로 차례로 따라 올라가, 타일이 놓여 있는 칸에 이르면 그 타일에 주목한다. 타일이 놓여 있는 칸이 없이 판의 끝에 다다르면 아무것도 주목하지 않는다.
- 같은 조작을 두드린 칸에서 아래, 왼쪽, 오른쪽 방향으로도 한다. 최대 4장의 타일이 주목된다.
- 주목한 타일 중 같은 색인 것이 있으면, 그 타일을 판에서 제거한다. 같은 색 타일의 짝이 2쌍 있으면, 그 둘 다 제거한다.
- 타일을 제거한 수와 같은 값의 점수를 얻는다.
- 주목을 멈춘다.
예를 들어, 다음과 같은 상황을 생각하자. 타일이 놓여 있지 않은 칸은 마침표로, 타일의 색은 알파벳 대문자로 나타낸다.
..A.......
.......B..
..........
..B.......
..A.CC....
여기서 위에서 2행, 왼쪽에서 3열의 칸을 두드리는 조작을 생각한다. 주목하게 되는 타일은 A, B, B 세 장이므로, B 두 장이 사라지고 판은 다음과 같이 되어 2점을 얻는다.
..A.......
..........
..........
..........
..A.CC....
이 퍼즐은 느긋하게 하면 시간이 다 되어 판의 일부가 보이지 않게 되고 수행이 얼마나 부족했는지 알 수 없게 된다. 각 색의 타일은 2장씩 놓여 있지만, 그것들을 모두 지울 수 있다고는 할 수 없으므로, 미리 프로그램에 점수의 최댓값을 계산하게 해 두고 싶다.
입력
M N
C1,1C1,2...C1,N
C2,1C2,2...C2,N
...
CM,1CM,2...CM,N
정수 M, N은 판이 세로 M × 가로 N의 칸이라는 것을 나타낸다. C**i, j는 알파벳 대문자 또는 마침표(.)이며, 위에서 i행, 왼쪽에서 j열의 칸에 대해 알파벳 대문자이면 놓여 있는 타일의 색을 나타내고, 마침표이면 이 칸에 타일이 놓여 있지 않음을 나타낸다.
1 ≤ M ≤ 500, 1 ≤ N ≤ 500을 만족한다. 각 알파벳 대문자는 입력 중에 0개 또는 2개 나타난다.
출력
점수의 최댓값을 1행에 출력하라.