Connect

Time limit5sMemory limit512 MB

Summary

Place each string in its row in order across the C columns so that the number of adjacent equal-letter cell pairs is maximized.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, String
Solved: No attempts yet

Problem

Connect is a solitaire puzzle that uses several letter tiles.

The table has $R \times C$ empty cells. For each $i$ $(1 \le i \le R)$ , you must put a string $s_i$ $(1 \le |s_i| \le C)$ in the $i$ -th row of the table. The letter order cannot change. In other words, choose an integer sequence $\{a_j\}$ with $1 \le a_1 < a_2 < \cdots < a_{|s_i|} \le C$ , and put the $j$ -th character of $s_i$ in column $a_j$ .

For example, when $C = 8$ and $s_i$ is "ICPC", you can place it like this:

I_C_P_C_
ICPC____
_IC___PC

'_' stands for an empty cell.

For each non-empty cell $x$ , you get one point for every adjacent cell that has the same character as $x$ . Two cells are adjacent if they share an edge. Find the maximum total point you can get.

Input

The first line contains two integers $R$ and $C$ $(1 \le R \le 128, 1 \le C \le 16)$ . Then $R$ lines follow, each containing a string $s_i$ $(1 \le |s_i| \le C)$ . All characters of $s_i$ are uppercase letters.

Output

Print the maximum total point in one line.

Examples3

Example 1
Input
```
2 4
ACM
ICPC
```
Expected output
```
2
```
Example 2
Input
```
2 9
PROBLEMF
CONNECT
```
Expected output
```
6
```

Example 3

Input

4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST

Expected output