در دنیای مورچه‌ها زندگی سختی‌های زیادی دارد. مورچه‌ها در فصل‌های گرم غذای لازم خود را برای فصول سرد سال در لانه‌های خود جمع‌آوری می‌کنند.

امسال با توجه به افزایش جمعیت و انبوه جمع‌آوری غذا مورچه‌ها با کمبود جا مواجه شده‌اند. سیستم انبار مورچه‌ها دارای $n$ ستون است که در یک ردیف کنار هم قرار دارند. در حال حاضر در ستون $i$ام، یک دسته‌ی $a_i$ گرمی گندم قرار دارد. مورچه‌ها قابلیت این را دارند که یک دسته گندم را از یک ستون برداشته و در یکی از ستون‌های مجاور آن ستون (ستون‌های چپ و راست آن در صورتی که موجود باشند) قرار دهند. ملکه مورچه‌ها دستوری صادر کرده است، مبنی بر این که مورچه‌ها باید در کم‌ترین زمان ممکن کاری کنند که حداکثر $k$ ستون از ستون‌های انبار، گندم داشته باشد(یعنی، حداقل $n-k$ ستون خالی می‌شود). انتقال یک دسته‌ی $x$ گرمی گندم از یک ستون، به ستون مجاور آن، $x$ ثانیه طول می‌کشد. هم‌چنین در هر لحظه می‌توان حداکثر یک دسته را جابه‌جا کرد. در ضمن نمی‌توان یک دسته گندم را به دسته‌های کوچک‌تر تقسیم کرد. به عنوان مثال اگر یک دسته‌ی ۳گرمی را به ستون مجاور انتقال دهیم و در آن ستون قبلا یک دسته‌ی ۵ گرمی وجود داشت، پس از انتقال یک دسته‌ی ۸ گرمی خواهیم داشت و دیگر نمی‌توان ۳ گرم را از ۵ گرم تفکیک نمود(مورچه‌ها مجبورند ۸ گرم را با هم حمل کنند).

برنامه‌ای بنویسید که:

• تعداد ستون‌های اولیه، تعداد ستون‌های نهایی و وزن دسته‌های گندم را از ورودی بخواند.
• کم‌ترین زمان ممکن برای جمع‌آوری دسته‌های گندم در $k$ ستون را به‌دست آورد.
• مقدار محاسبه شده را در خروجی بنویسید.

• در سطر اول ورودی، دو عدد صحیح $n$ و $k$ نوشته شده‌اند($1\leq n \leq 1200$ و $1\leq k \leq 100$).
• در سطر دوم، $n$ عدد صحیح آمده است که با فاصله از هم جدا شده‌اند. عدد $i$ام $a_i$ (وزن $i$امین دسته‌ی گندم) را مشخص می‌کند.

در تنها سطر خروجی یک عدد بنویسید که مشخص‌کننده‌ی کم‌ترین زمان ممکن برای جمع‌آوری دسته‌های گندم در $k$ ستون می‌باشد. این عدد را بر حسب ثانیه بنویسید.

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

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