Connect

시간 제한5초메모리 제한512 MB

요약

각 행에 문자열을 순서대로 놓고, 같은 글자가 상하좌우로 인접한 칸 쌍이 가장 많아지는 배치를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 문자열
정답자: 아직 제출이 없습니다

문제

퍼즐 'Connect'는 글자 타일 여러 개를 사용하는 혼자 하는 퍼즐이다.

표에 $R \times C$ 개의 빈 칸이 있다. 각 $i$ $(1 \le i \le R)$ 에 대해 문자열 $s_i$ $(1 \le |s_i| \le C)$ 를 표의 $i$ 번째 행에 넣어야 한다. 문자의 순서는 바꿀 수 없다. 즉, $1 \le a_1 < a_2 < \cdots < a_{|s_i|} \le C$ 를 만족하는 정수 수열 $\{a_j\}$ 를 고르고, $s_i$ 의 $j$ 번째 문자를 $a_j$ 번째 열에 놓는다.

예를 들어 $C = 8$ 이고 $s_i$ 가 "ICPC"이면 다음과 같이 놓을 수 있다.

I_C_P_C_
ICPC____
_IC___PC

'_'는 빈 칸을 나타낸다.

비어 있지 않은 칸 $x$ 마다, $x$ 와 같은 문자를 가진 인접 칸의 개수만큼 점수를 얻는다. 두 칸은 변을 공유하면 인접한 것이다. 얻을 수 있는 점수 합의 최댓값을 구하라.

입력

첫 줄에 두 정수 $R$ 과 $C$ $(1 \le R \le 128, 1 \le C \le 16)$ 가 주어진다. 이후 $R$ 개의 줄에 각각 문자열 $s_i$ $(1 \le |s_i| \le C)$ 가 주어진다. $s_i$ 의 모든 문자는 대문자 알파벳이다.

출력

점수 합의 최댓값을 한 줄에 출력한다.

예제3

예제 1
입력
```
2 4
ACM
ICPC
```
예상 출력
```
2
```
예제 2
입력
```
2 9
PROBLEMF
CONNECT
```
예상 출력
```
6
```

예제 3

입력

4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST

예상 출력