# Connect

You are playing a solitaire puzzle called "Connect", which uses several letter tiles.

There are `R × C` empty cells.
For each `i` `(1 ≤ i ≤ R)`, you must put a string `s`_{i} `(1 ≤ |s`_{i}| ≤ C) in the `i`-th row of the table, without changing the letter order.
In other words, you choose an integer sequence `{a`_{j}} such that
`1 ≤ a`_{1} < a_{2} < ... < a_{|si|} ≤ C
, and put the `j`-th character of the string `s`_{i} in the `a`_{j}-th column `(1 ≤ j ≤ |s`_{i}|).

For example, when `C = 8` and `s`_{i} = "ICPC", you can put `s`_{i} like followings.

I_C_P_C_
ICPC____
_IC___PC

'_' represents an empty cell.

For each non-empty cell `x`, you get a point equal to the number of adjacent cells which have the same character as `x`.
Two cells are adjacent if they share an edge.

Calculate the maximum total point you can get.

## Input

The first line contains two integers `R` and `C` `(1 ≤ R ≤ 128, 1 ≤ C ≤ 16)`.

Then `R` lines follow, each of which contains `s`_{i}
`(1 ≤ |s`_{i}| ≤ C).
All characters of `s`_{i} are uppercase letters.

## Output

Output the maximum total point in a line.

## Sample Input 1

2 4
ACM
ICPC

## Output for the Sample Input 1

2

## Sample Input 2

2 9
PROBLEMF
CONNECT

## Output for the Sample Input 2

6

## Sample Input 3

4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST

## Output for the Sample Input 3

18