+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $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 ``` در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

حل سؤال در بانک سؤالات