یک سمفونی موسیقی دنباله‌ای از نت‌های موسیقی است به طوری که هر نت یک حرف از حروف الفبای انگلیسی می‌باشد (این حروف می‌توانند بزرگ یا کوچک باشد یعنی در مجموع ۵۲ نت مختلف داریم) با توجه به طولانی بودن سمفونی‌ها و تکراری بودن نت‌ها موسیقی‌دان‌ها از روش‌هایی برای فشرده کردن طول سمفونی استفاده می‌کنند به این صورت که فرض کنید سمفونی مورد نظر به صورت یک رشته از حروف الفبای انگلیسی داده شده هر خانه‌ی رشته فشرده شده به دو صورت می‌تواند باشد یا یک حرف از رشته‌ی ورودی است و یا به صورت $(a-b)$ می‌باشد که در آن $a$ و $b$‌دو عدد صحیح هستند به این معنی که در این بخش از حرف $a$ ام تا حرف $b$ ام رشته‌ی ورودی تکرار می‌شوند (خانه‌های رشته‌ی ورودی از یک شماره‌گذاری می‌شوند). $b$ از $a$ بزرگ‌تر است و باید طوری باشد که زیر رشته‌ی اصلی را ساخت. فرض کنید هزینه‌ی نگهداری خانه‌های عادی برابر یک و هزینه‌ی خانه‌های نوع دوم برابر $k$‌ باشد. هدف این مسئله نوشتن برنامه‌ای است که با گرفتن یک رشته‌ی ورودی رشته فشرده شده‌ی آن با کم‌ترین هزینه را به ما بدهد.

فایل ورودی دو سطر دارد در سطر اول عدد $k$‌ نوشته شده و در سطر بعد رشته‌ی ورودی آمده است. (عدد $k$ یک عدد صحیح مثبت است و حداکثر ۱۰۰۰ می‌باشد طول رشته‌ی ورودی نیز از ۱۰۰۰۰ حرف بیش‌تر نیست.)

فایل خروجی شامل دو سطر می‌باشد در سطر اول ابتدا تعداد خانه‌های رشته‌ی فشرده شده و سپس کل هزینه‌ی آن نوشته شده است در سطر بعدی نیز رشته‌‌ی فشرده شده با فرمت بالا آمده است. (بین کاراکترها هیچ کاراکتر اضافی مثل $space$ وجود ندارد)

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۷۴۳ کیلو بایت

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