Каравани#1894
"Вітаю. Я Кирило. Хотів би, щоб ви розробили 3D екшн-гру з таким концептом... Гравці можуть вибирати, ким грати: лісовими ельфами, палацовими стражниками чи злодієм. Якщо грати за ельфів, вони мешкають у лісі в дерев'яних будинках, на них нападають палацові солдати і злодії. Гравці можуть нападати на каравани... [пропущено] P.S. Я вже два роки хочу таку гру."
Лист до ігрової компанії MiST land
Природно, Петрик під час розробки не міг залишити поза увагою побажання світового ігрового товариства. Тому у його грі гравці можуть "нападати" і "грабувати каравани". Караван складається з возів, у кожному з яких знаходиться певна кількість золота. Напад можна почати з будь-якого воза, а потім продовжити до сусіднього вперед або назад, збираючи золото. Операцію слід виконати швидко, інакше прибудуть охоронці й схоплять грабіжників. Тому пограбувати всі вози не вдасться.
Коля, який, як і слід було очікувати, грає за ельфів, знає кількість возів у каравані , скільки золота знаходиться у кожному возі (у -му возі знаходиться a_i золота) та максимальну кількість возів , які його загін може пограбувати до прибуття охоронців. Він повинен визначити, яку максимальну кількість золота можна отримати під час нападу.
У першому рядку містяться два цілі числа і (1 \leq k \leq N \leq 100000) — кількість возів у каравані та максимальна кількість возів, які можна пограбувати. У другому рядку розташовано цілих чисел a_i — кількість золота у кожному возі (0 \leq a_i \leq 10000).
Виведіть у єдиному рядку максимальну суму золота, яку можна отримати під час нападу.
Приклад 1