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