You are playing a solitaire puzzle called "Connect", which uses several letter tiles. There are \textbf{R}×\textbf{C} empty cells. For each \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{R}), you must put a string \textbf{s_i} (\textbf{1} ≤ \textbf{|s_i|} ≤ \textbf{C}) in the \textbf{i}-th row of the table, without changing the letter order. In other words, you choose an integer sequence \textbf{a_j} such that \textbf{1} ≤ \textbf{a_1} < \textbf{a_2} <…< \textbf{a_\{|si|\}} ≤ \textbf{C}, and put the \textbf{j}-th character of the string \textbf{s_i} in the \textbf{a_j}-th column (\textbf{1} ≤ \textbf{j} ≤ \textbf{|s_i|}). For example, when \textbf{C = 8} and \textbf{si = "ICPC"}, you can put \textbf{s_i} like followings. \textbf{I_C_P_C_} \textbf{ICPC____} \textbf{_IC___PC} '\textbf{_}' represents an empty cell. For each non-empty cell \textbf{x}, you get a point equal to the number of adjacent cells which have the same character as \textbf{x}. Two cells are adjacent if they share an edge. Calculate the maximum total point you can get. \InputFile The first line contains two integers \textbf{R} and \textbf{C} (\textbf{1} ≤ \textbf{R} ≤ \textbf{128}, \textbf{1} ≤ \textbf{C} ≤ \textbf{16}). Then \textbf{R} lines follow, each of which contains \textbf{s_i} (\textbf{1} ≤ \textbf{|s_i|} ≤ \textbf{C}). All characters of \textbf{s_i} are uppercase letters. \OutputFile Output the maximum total point in a line.