eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Караваны

Караваны

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

"Здраствуйте. Я, Кирило. Хотів би щоб ви задєлали гру, 3Д-екшон суть такова... Пользователь може грати лісними ельфами, охраною дворця і злодійом. І якщо пользователь грає нльфами то ельфы у лісу, домики деревяні набігають солдати дворця і злодії. Можна грабить коровани... [skipped] P.S. Я джва года хочу таку ігру.

Лист у компанію по розробці ігор MiST land

Ну і звичайно ж Петрик не міг при розробці не врахувати побажань світової геймерської співдружності, тому у його грі можна "набігати" и "грабить коровани". Караван складається з повозок, у кожній з яких знаходиться певна кількість золота. Пограбування можна почати з довільної повозки, просуваючись далі до наступної чи попередньої і забираючи золото, яке знаходиться у них. Всю операцію потрібно провести достатньо швидко, інакше підіспіє охорона і схопить грабіжників. Тому забрати можна буде не з усіх повозок.

Коля, який грає, як і слід було очікувати, за ельфів, знає і кількість повозок у каравані N, і скільки золота у кожній повозці (у i-ій повозці знаходиться a_i золота), і максимальну кількість повозок k, яку його загін успіє обійти до прибуття охорони. Йому необхідно взнати максимальну кількість золота, яку він може отримати в результаті операції.

Вхідні дані

В первой строке заданы два целых числа N и k (1kN100000), определяющие размер каравана и максимальное число повозок, которые можно ограбить. Во второй строке задаются N целых чисел a_i, определяющие количество золота в повозках (0a_i10000).

Вихідні дані

У єдиному рядку виведіть найбільшу суму, яку може принести пограбування.

Приклад

Вхідні дані #1
7 3
3 2 1 2 3 2 1
Вихідні дані #1
7
Автор Віталій Неспірний
Джерело Зимова Школа, Харків 2011, День 6