Connect

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

There are 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, without changing the letter order. In other words, you choose an integer sequence a_j such that 1 \le a_1 < a_2 < \ldots < a_{|s_i|} \le C, and put the $j$-th character of the string s_i in the a_j-th column (1 \le j \le |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 points you can get.