فریدون ‎$n$‎ گاو وحشی خریده‌ است و آن‌ها را در ‎$n$‎ اسطبل مجزا که در یک خط کنار هم قرار گرفته‌اند، نگه‌داری می‌کند. هر کدام از ‎$n$‎ گاو برای فریدون ارزش خاصی دارند که این ارزش یک عدد صحیح (مثبت، صفر یا منفی) است (‎ارزش منفی به‌معنی انزجار است؛ اما فریدون زورش به گاوها (ولو منزجرکننده‌ترینشان) نمی‌رسد که آن‌ها را بیرون بیاندازد). متأسفانه این اسطبل‌ها در ندارند و تنها از ‎$3$‎ طرف محصور هستند. فریدون می‌خواهد با یک هزینه بهینه از فرار شبانه بعضی از گاوها جلوگیری کند تا در نهایت بیش‌ترین سود را به‌دست بیاورد.

فریدون یک دوست نجار به‌نام منوچهر دارد که هرلحظه حاضرست در قبال دریافت ‎$k$‎ واحد پول، یک نوار چوبی دراز (به هر طولی) بسازد. فریدون می‌تواند با قرار دادن یک نوارچوبی (با طول مناسب) در جلوی یک اسطبل یا چند اسطبل متوالی از فرار گاوهای آن اسطبل‌ها جلوگیری کند. به عبارت دیگر هر نوار چوبی (با هزینه ثابت ‎$k$‎) تنها یک بازه‌ی بسته از استطبل‌ها را دربسته می‌کند. نیز می‌دانیم هر اسطبلی که درش باز بماند گاو آن اسطبل حتماً فرار می‌کند‎!‎

به فریدون کمک کنید که طوری تعدادی نوار چوبی خریداری کرده و در جاهای مناسب نصب کند که بیش‌ترین سود را ببرد. سودی که فریدون می‌برد برابرست با مجموع ارزش گاوهای محصور شده در اسطبل‌شان (توسط نوارهای چوبی) منهای هزینه نوارهای چوبی (‎$k$‎ ضرب‌در تعداد نوارها).

• در سطر اول ورودی دو عدد ‎$n$‎ و سپس ‎$k$‎ آمده است.
• در سطر دوم ‎$n$‎ عدد صحیح آمده است که عدد ‎$i$‎اُم (با شمارش از ‎$1$) ارزش گاو قرارگرفته در اسطبل ‎$i$‎اُم را نشان می‌دهد.
• $1 \leq n \leq 100,000$‎ ولی در ‎$80$‎ درصد تست‌ها ‎$1 \leq n \leq 10,000$‎ است.
• $0 \leq k \leq 1000$‎ و ارزش گاوها در بازه‌ی ‎$[-2000‎, ‎2000]$‎ قرار دارند.

بیش‌ترین سودی که فریدون می‌تواند به‌دست بیاورد را در یک سطر بنویسید.

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

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