eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Соединение

Соединение

Лимит времени 5 секунд
Лимит использования памяти 64 MiB

Вы играете в головоломку - пасьянс под названием "Соединение", в которой используется несколько букв - плиток.

Имеется R×C пустых ячеек. Для каждого i (1iR) необходимо вставить строку s_i (1|s_i|C) в i-ую строку таблицы без изменения порядка букв. Другими словами необходимо выбрать такую целочисленную последовательность a_j, что 1a_1 < a_2 <…< a_{|si|}C, и вставить j-ый символ строки s_i в a_j-ую колонку (1j|s_i|).

Например, если C = 8 и s_i = "ICPC", можно вставить s_i одним из следующих методов:

I_C_P_C_

ICPC____

_IC___PC

'_' представляет собой пустую ячейку.

Для каждой непустой ячейки x Вы получаете количество балов, равное числу соседних ячеек содержащих ту же букву что и x. Две ячейки являются соседними, если у них общая сторона.

Вычислить наибольшее количество баллов, которое Вы сможете получить.

Входные данные

Первая строка содержит два целых числа R и C (1R128, 1C16). Далее следуют R строк, каждая из которых содержит s_i (1|s_i|C). Все символы s_i являются заглавными буквами.

Выходные данные

Вывести наибольшее количество балов, которое можно получить.

Пример

Входные данные #1
2 4
ACM
ICPC
Выходные данные #1
2
Источник JAG Summer 2012, Japan