روحا… پس از چندین سال تجربه در المپیاد، فهمید که «نون توی گله!»
بنابراین تصمیم گرفت باغچهای اجاره کند و در آن گلهای زیبا بکارد و پس از آن که رشد کردند، آنها را به مردم بفروشد.
باغچهای که او اجاره کرد به شکل یک مستطیل $n$ در $m$ است. این مستطیل را به شکل جدولی در نظر بگیرید که $n$ سطر و $m$ ستون دارد و در هر خانه از آن جدول میتوان یک گل کاشت. سطرهای جدول به ترتیب از بالا به پایین با $1$ تا $n$ و ستونهای جدول از چپ به راست به ترتیب با $1$ تا $m$ شمارهگذاری شدهاند.
گلهای مورد نظر روحا… $26$ نوع دارند. هر یک از این انواع را با یکی از حروف $A$ تا $Z$ نمایش میدهیم. همچنین او میخواهد در سطر $i$ام باغچهاش گلهایی را بکارد که با رشتهای به نام $s_i$ نمایششان میدهیم. ممکن است طول این رشته از $m$ کمتر باشد. در این صورت او مجبور است تعدادی از خانههای باغچه را در آن سطر خالی بگذارد. برای او فقط ترتیب گلها در هر سطر مهم است. یعنی اگر خانههای خالی سطر $i$ام را حذف کنیم و به ازای خانههای باقیمانده به ترتیب از چپ به راست نوعشان را بنویسیم، رشتهای برابر $s_i$ حاصل خواهد شد.
از نظر روحا… هر باغچه یک مقدار شادابی دارد! شادابی یک روش از کاشتن گلها، برابر تعداد جفت خانههای مجاور ضلعی است که نوع گل کاشته شده در آنها یکسان باشد.
مثلا اگر یک جدول $2 \times 2$ داشته باشیم و $s_1 = s_2 = A$ باشد، اگر گلها را در خانهی اوّل سطر اوّل و خانهی دوم سطر دوم بکاریم، شادابی برابر $0$ میشود. امّا اگر آنها را در خانههای دوم دو سطر بکاریم، شادابی باغچهی حاصل برابر $1$ میشود. همچنین اگر $s_1 = AA$ و $s_2 = BB$ باشد، روحا… فقط به یک طریق میتواند گلها را بکارد و شادابی حاصل نیز برابر $2$ خواهد بود.
روحا… میخواهد طوری گلها را بکارد که با شرایط مذکور، شادابی باغچه بیشینه شود. امّا او که از المپیاد کنارهگیری کردهاست، به نظرش این سوال خیلی المپیادی است و از شما میخواهد حلش کنید.
در سطر اوّل $2$ عدد $n$ و $m$ آمدهاند.
در هر یک از $n$ سطر بعد، یک رشتهی ناتهی شامل حروف $A$ تا $Z$ آمدهاست که $i$امین رشته، نمایانگر $s_i$ است.
در تنها سطر خروجی، بیشینه شادابی ممکن باغچه را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
1 1 B | 0 |
2 12 A B | 0 |
3 3 B AB A | 2 |
نمونهی سوم: میتوان در خانهی سوم از دو سطر اوّل و دوم گلی از نوع $B$ کاشت و در خانهی اوّل از دو سطر دوم و سوم گلی از نوع $A$ کاشت.