معلم محمد به او مشق داده که درس کتاب را از رو بنویسد. هنگامی که محمد دارد مشقش را می‌نویسد، در صورتی که یک کلمه باکلمه‌ای که در سطر قبلی درست بالای آن قرار گرفته یکسان باشد، محمد می‌تواند آن را ننویسد و به جایش یک ایضا در آن مکان قرار دهد؛ در زیر یک ایضا هم می‌تواند ایضا قرار بگیرد، البته در صورتی که دو کلمه‌ای که به جایشان ایضا گذاشتیم یکسان باشند. در هر سطر از دفتر مشق محمد می‌توان به هر تعداد دلخواهی قبل و بعد از هر کلمه یا ایضا، فاصله قرار داد؛ ولی در هر سطر حداکثر $m$ کلمه یا ایضا جا می‌شود.

از آن‌جایی که محمد انسان تنبلی است، دوست دارد که تا حد امکان سریع مشقش را بنویسد؛ به همین دلیل دوست دارد به گونه‌ای متن را بنویسد که از بیش‌ترین تعداد ایضا استفاده کند. آیا می‌توانید به او در این راه کمک کنید؟

برنامه‌ای بنویسید که:

• متن مشق محمد و بیش‌ترین تعداد کلماتی که در یک سطر از دفتر محمد جا می‌شود را از ورودی بخواند.
• روشی از چیدمان کلمات را بیابید که بیش‌ترین تعداد ایضا را داشته باشد.
• پاسخ را در خروجی بنویسید.

در سطر نخست ورودی یک عدد صحیح $n$ نوشته شده است که تعداد کلمات مشق محمد را نشان می‌دهد ($1\leq n\leq 3000$). در سطر دوم یک عدد $m$ نوشته شده که بیش‌ترین تعداد کلمه‌ای است که محمد در یک سطر می‌تواند بنویسد و $1\leq m\leq 40$ است. در هر یک از $n$ سطر بعدی یک کلمه نوشته شده است. طول کلمه‌ها حداکثر ۱۰ حرف است و کلمه‌ها از حروف کوچک الفبای انگلیسی ساخته شده‌اند.

در تنها سطر خروجی یک عدد بنویسید که نشان‌دهنده‌ی بیش‌ترین تعداد ایضا است که می‌توان در نوشتن متن به کار برد.

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

• سوال بعد
• سوال قبل