Командна робота#10401
На свято, яке дуже любить фермер Джон, він хоче надіслати подарунки своїм друзям. Оскільки він не дуже вправний у пакуванні подарунків, він вирішує залучити на допомогу своїх корів. Як можна було очікувати, корови самі по собі не набагато кращі у пакуванні подарунків — урок, який фермеру Джону доведеться засвоїти на власному гіркому досвіді.
У фермера Джона є корів, що стоять у ряд і зручно пронумеровані від до по порядку. Корова має рівень майстерності пакування подарунків s_i. Ці рівні майстерності можуть суттєво відрізнятися, тому ФД вирішує розділити своїх корів на команди. Команда може складатися з будь-якої групи щонайбільше послідовних корів, і жодна корова не може належати більш ніж до однієї команди. Оскільки корови вчаться одна в одної, рівень майстерності кожної корови в команді можна підняти до рівня майстерності найвправнішої корови цієї команди.
Допоможіть ФД визначити максимально можливу суму рівнів майстерності, яку він може отримати, оптимально сформувавши команди.
Перший рядок містить два цілих числа та k~(1 \le n \le 10^4, 1 \le k \le 10^3). Кожен з наступних рядків містить рівень майстерності однієї корови в тому порядку, в якому стоять корови. Кожен рівень майстерності є додатним цілим числом, що не перевищує 10^5.
Виведіть одне ціле число — максимально можливу суму рівнів майстерності, яку ФД може отримати, розділивши корів на команди з послідовних корів.
У цьому прикладі оптимальним розв'язком є об'єднання перших корів та останніх корів, залишивши середню корову в команді самостійно (нагадуємо, що команди з меншою за кількістю корів дозволені). У результаті рівні майстерності корів стають , , , , , , , що в сумі дає .
Приклад 1