Соединение
Вы играете в головоломку - пасьянс под названием "Соединение", в которой используется несколько букв - плиток.
Имеется R×C пустых ячеек. Для каждого i (1 ≤ i ≤ R) необходимо вставить строку s_i (1 ≤ |s_i| ≤ C) в i-ую строку таблицы без изменения порядка букв. Другими словами необходимо выбрать такую целочисленную последовательность a_j, что 1 ≤ a_1 < a_2 <…< a_{|si|} ≤ C, и вставить j-ый символ строки s_i в a_j-ую колонку (1 ≤ j ≤ |s_i|).
Например, если C = 8 и s_i = "ICPC", можно вставить s_i одним из следующих методов:
I_C_P_C_
ICPC____
_IC___PC
'_' представляет собой пустую ячейку.
Для каждой непустой ячейки x Вы получаете количество балов, равное числу соседних ячеек содержащих ту же букву что и x. Две ячейки являются соседними, если у них общая сторона.
Вычислить наибольшее количество баллов, которое Вы сможете получить.
Входные данные
Первая строка содержит два целых числа R и C (1 ≤ R ≤ 128, 1 ≤ C ≤ 16). Далее следуют R строк, каждая из которых содержит s_i (1 ≤ |s_i| ≤ C). Все символы s_i являются заглавными буквами.
Выходные данные
Вывести наибольшее количество балов, которое можно получить.