• محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

روح‌ا... پس از چندین سال تجربه در المپیاد، فهمید که «نون توی گله!»

بنابراین تصمیم گرفت باغچه‌ای اجاره کند و در آن گل‌های زیبا بکارد و پس از آن که رشد کردند، آن‌ها را به مردم بفروشد.

باغچه‌ای که او اجاره کرد به شکل یک مستطیل nn در mm است. این مستطیل را به شکل جدولی در نظر بگیرید که nn سطر و mm ستون دارد و در هر خانه از آن جدول می‌توان یک گل کاشت. سطرهای جدول به ترتیب از بالا به پایین با 11 تا nn و ستون‌های جدول از چپ به راست به ترتیب با 11 تا mm شماره‌گذاری شده‌اند.

گل‌های مورد نظر روح‌ا... 2626 نوع دارند. هر یک از این انواع را با یکی از حروف AA تا ZZ نمایش می‌دهیم. همچنین او می‌خواهد در سطر iiام باغچه‌اش گل‌هایی را بکارد که با رشته‌ای به نام sis_i نمایششان می‌دهیم. ممکن است طول این رشته از mm کم‌تر باشد. در این صورت او مجبور است تعدادی از خانه‌های باغچه را در آن سطر خالی بگذارد. برای او فقط ترتیب گل‌ها در هر سطر مهم است. یعنی اگر خانه‌های خالی سطر iiام را حذف کنیم و به ازای خانه‌های باقی‌مانده به ترتیب از چپ به راست نوعشان را بنویسیم، رشته‌ای برابر sis_i حاصل خواهد شد.

از نظر روح‌ا... هر باغچه یک مقدار شادابی دارد! شادابی یک روش از کاشتن گل‌ها، برابر تعداد جفت خانه‌های مجاور ضلعی است که نوع گل کاشته شده در آن‌ها یکسان باشد.

مثلا اگر یک جدول 2×22 \times 2 داشته باشیم و s1=s2=As_1 = s_2 = A باشد، اگر گل‌ها را در خانه‌ی اوّل سطر اوّل و خانه‌ی دوم سطر دوم بکاریم، شادابی برابر 00 می‌شود. امّا اگر آن‌ها را در خانه‌های دوم دو سطر بکاریم، شادابی باغچه‌ی حاصل برابر 11 می‌شود. همچنین اگر s1=AAs_1 = AA و s2=BBs_2 = BB باشد، روح‌ا... فقط به یک طریق می‌تواند گل‌ها را بکارد و شادابی حاصل نیز برابر 22 خواهد بود.

روح‌ا... می‌خواهد طوری گل‌ها را بکارد که با شرایط مذکور، شادابی باغچه بیشینه شود. امّا او که از المپیاد کناره‌گیری کرده‌است، به نظرش این سوال خیلی المپیادی است و از شما می‌خواهد حلش کنید.

ورودی

در سطر اوّل 22 عدد nn و mm آمده‌اند.
در هر یک از nn سطر بعد، یک رشته‌‌ی ناتهی شامل حروف AA تا ZZ آمده‌است که iiامین رشته، نمایان‌گر sis_i است.

  • 1n1281 \le n \le 128
  • 1m161 \le m \le 16
  • 1sim1 \le |s_i| \le m

خروجی

در تنها سطر خروجی، بیشینه شادابی ممکن باغچه را چاپ کنید.

زیر مسئله ها

زیرمسئله نمره محدودیت ها
۱ ۱۱ n100,m8n \le 100, m \le 8
۲ ۱۳ n100,m11n \le 100, m \le 11
۳ ۷۶ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

1 1
B
Plain text

خروجی نمونه ۱

0
Plain text

ورودی نمونه ۲

2 12
A
B
Plain text

خروجی نمونه ۲

0
Plain text

ورودی نمونه ۳

3 3
B
AB
A
Plain text

خروجی نمونه ۳

2
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.