- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
عمو که فردی بسیار پول پرست است، جهت صرفهجویی در تعداد حروف پیامکهایش به فشردهسازی رشتهها روی آورده.
روش عمو برای فشردهسازی به این صورت است:
او در ابتدا جایگشتی از اعداد ۱, ۲, ..., \(k\) انتخاب میکند. سپس رشتهی خود را به دسته های پشت سر هم \(k\) حرفی تقسیم میکند (طول رشته باید به \(k\) بخشپذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشتهی بدست آمده را بوسیلهی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند.
اعمال جایگشت \(p\) روی یک دسته از \(k\) حرف یعنی حرف \(p_1\)م را در جایگاه اول قرار داده، حرف \(p_2\)م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشتهی \(abcd\) آن را تبدیل به \(cadb\) میکند. اعمال این جایگشت با دسته دسته کردن روی رشتهی \(abcdefgh\)، رشتهی \(cadbgehf\) را نتیجه میدهد.
رشتهی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشتهی فشردهشده را برابر تعداد گروه حرفهای برابر پشت سر هم درنظر میگیریم. برای مثال طول رشتهی \(aabcaa\) پس از فشردهشدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a)
عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشتهی نهایی به جایگشت انتخابشده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشردهسازی بوسیلهی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید.
ورودی
سطر اول تنها شامل عدد \(k\) است.
در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است.
\[2 \le k \le 16\]
خروجی
در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است.
مثال
ورودی نمونه ۱
4
abcabcabcabc
خروجی نمونه ۱
7
در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجهی بهینه بدست میآید.