یانگوم بعد از گرفتن دکترا در آشپزی با نام پژوهش «چگونگی تهیه پیتزا» و گرفتن دکترای دیگر در زمینه پزشکی برای پیدا کردن درمان برای بیماری‌های ایدز و آلزایمر ، تصمیم گرفته است تا یک مسئله حل نشده در زمینه نظریه اطلاعات که حتی شانون (پدر نظریه اطلاعات) هم از حل آن ناتوان بوده است را حل کند. او می‌خواهد زبانی با $n$ لغت با استفاده از $d$ حرف $c_1, c_2, …, c_d$ بسازد. این زبان باید پیشوند آزاد باشد. زبان پیشوند آزاد زبانی است که در آن هیچ دو لغت ($s, t$) وجود ندارد که $s$ پیشوند $t$ باشد. هزینه استفاده از حرف $w_i$ ، $c_i$ است. هزینه لغت $s$ که طول آن برابر l است ، برابر است با جمع هزینه تمام $l$ حرف آن. برای مثال ، اگر $c_1=a; c_2=b; w_1=1; w_2=10$ هزینه لغت «$aba$» برابر است با $1+10+1=12$ . به طور مشابه هزینه یک زبان با $n$ لغت برابر است با جمع هزینه‌های $n$ لغت آن. برای مثال، هزینه زبان “$ab$”; “$bbb$”; “$baaa$” برابر است با $11+30+13=54$ . مشابه کارهای قبلی، یانگوم می‌خواهد این کار را هم به بهترین شکل ممکن انجام دهد یعنی او می‌خواهد یک زبان پیشوند آزاد با $n$ لغت با کم‌ترین هزینه ممکن درست کند.

• ورودی از چند سناریو تشکیل شده است. در خط اول هر سناریو دو عدد $n$ ≤ ۲۰۰ ) $n$ ) و $d$ ≤ ۲۰۰ ) $d$ ) آمده است.
• در خط بعدی اعداد غیر منفی $w_1,w_2, …, w_d$ آمده است.
• ورودی با خطی شامل دو عدد صفر تمام می شود.

برای هر سناریو، شما باید کم‌ترین هزینه برای ساختن زبان پیشوند آزاد با $n$ لغت و $d$ حرف را چاپ کنید.

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

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