З'єднання

Ви граєте в головоломку-пасьянс під назвою "З'єднання", де використовуються кілька букв-плиток.

У вас є 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 є великими літерами.

Вихідні дані

Виведіть максимальну кількість балів, яку можна отримати.

Приклади