Bağlantı#5838
Siz "Birləşmə" adlı bir tapmaca - pasyans oynayırsınız və burada bir neçə hərf - plitələrdən istifadə edirsiniz.
R×C ölçüsündə boş hüceyrələr var. Hər bir i (1 ≤ i ≤ R) üçün s_i (1 ≤ |s_i| ≤ C) sətrini i-ci sıraya hərflərin sırasını dəyişmədən yerləşdirməlisiniz. Başqa sözlə, elə bir tam ədədlər ardıcıllığı a_j seçməlisiniz ki, 1 ≤ a_1 < a_2 <…< a_{|si|} ≤ C və s_i sətrinin j-ci simvolunu a_j-ci sütuna yerləşdirəsiniz (1 ≤ j ≤ |s_i|).
Məsələn, əgər C = 8 və s_i = "ICPC" olarsa, s_i aşağıdakı üsullardan biri ilə yerləşdirilə bilər:
I_C_P_C_
ICPC____
_IC___PC
'_' boş hüceyrəni təmsil edir.
Hər bir boş olmayan hüceyrə x üçün, x ilə eyni hərfi ehtiva edən qonşu hüceyrələrin sayına bərabər olan xal alırsınız. İki hüceyrə qonşu sayılır, əgər onların ümumi tərəfi varsa.
Əldə edə biləcəyiniz ən yüksək xal sayını hesablayın.
Birinci sətir iki tam ədəd R və C (1 ≤ R ≤ 128, 1 ≤ C ≤ 16) ehtiva edir. Sonra R sətir gəlir, hər biri s_i (1 ≤ |s_i| ≤ C) ehtiva edir. Bütün s_i simvolları böyük hərflərdir.
Əldə edilə biləcək ən yüksək xal sayını çıxarın.
Nümunə 1