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 si = "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.