+ محدودیت زمان: 1 ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در یک سرزمین دور، دختری به نام یانگوم زندگی می‌کرد که به ساخت زبان‌های جدید علاقه‌مند بود. او تصمیم گرفت زبانی به اسم یانگومی بسازد که شامل $n$ کلمه با $k$ حرف مشخص باشد. اما این زبان باید ویژگی خاصی داشته باشد هیچ کلمه‌ای نباید پیشوند اولیه کلمه دیگری باشد. به این ترتیب، یانگوم باید به دقت انتخاب کند که کلمات را چگونه بسازد. همچنین هر حرفی که یانگوم انتخاب می‌کرد، هزینه‌ای داشت. برای مثال، اگر حرف اول $x$ با هزینه ۵ و حرف دوم $y$ با هزینه ۴ باشد، هزینه کلمه "$xy$" برابر با ۵ + ۴ = ۹ بود. یانگوم می‌خواست زبان یانگومی $n$ کلمه ای متشکل از $k$ حرف بسازد که هیچ دوحرفی پیشوند یکدیگر نباشد و همچنین مجموع هزینه ساخت کلمات کمترین هزینه ممکن را داشته باشد. # ورودی در سطر اول دو عدد صحیح $n$ و $k$ که به ترتیب نمایانگر تعداد کلمات و حروف است داده میشوند. که $$1 \leq n \leq 200$$ $$2 \leq k \leq 200$$ سپس در خط بعدی، هزینه‌های مربوط به هر حرف داده می‌شد. # خروجی حداقل هزینه ساخت زبان یانگومی با $n$ کلمه و $k$ حرف را محاسبه کنید و نمایش دهید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 5 20 ``` ## خروجی نمونه ۱ ``` 16 ``` برای مثال بالا اگر فرض کنیم حروف به ترتیب $a, b, c$ هستند جواب مطلوب به صورت$ b,ab,aa$ که برابر ۵ + ۴ + 7 که برابر $16$ میشود.