З'єднання#5838
Ви граєте в головоломку-пасьянс під назвою "З'єднання", де використовуються кілька букв-плиток.
У вас є R \times C порожніх клітинок. Для кожного рядка (1 \le i \le R) потрібно вставити рядок s_i (1 \le |s_i| \le C) в -ий рядок таблиці, зберігаючи порядок букв. Тобто, потрібно вибрати таку цілочисельну послідовність a_j, що 1 \le a_1 < a_2 < \ldots < a_{|s_i|} \le C, і вставити -ий символ рядка s_i в a_j-у колонку (1 \le j \le |s_i|).
Наприклад, якщо C = 8 і s_i = "ICPC", можна вставити s_i одним із таких способів:
I_C_P_C_
ICPC____
_IC___PC
'_' позначає порожню клітинку.
Для кожної непорожньої клітинки ви отримуєте кількість балів, що дорівнює числу сусідніх клітинок, які містять ту ж букву, що і . Дві клітинки вважаються сусідніми, якщо у них є спільна сторона.
Вам потрібно обчислити максимальну кількість балів, яку ви можете отримати.
Перший рядок містить два цілі числа і (1 \le R \le 128, 1 \le C \le 16). Далі йдуть рядків, кожен з яких містить s_i (1 \le |s_i| \le C). Всі символи s_i є великими літерами.
Виведіть максимальну кількість балів, яку можна отримати.
Приклад 1