Караваны
"Здраствуйте. Я, Кирило. Хотів би щоб ви задєлали гру, 3Д-екшон суть такова... Пользователь може грати лісними ельфами, охраною дворця і злодійом. І якщо пользователь грає нльфами то ельфы у лісу, домики деревяні набігають солдати дворця і злодії. Можна грабить коровани... [skipped] P.S. Я джва года хочу таку ігру.
Лист у компанію по розробці ігор MiST land
Ну і звичайно ж Петрик не міг при розробці не врахувати побажань світової геймерської співдружності, тому у його грі можна "набігати" и "грабить коровани". Караван складається з повозок, у кожній з яких знаходиться певна кількість золота. Пограбування можна почати з довільної повозки, просуваючись далі до наступної чи попередньої і забираючи золото, яке знаходиться у них. Всю операцію потрібно провести достатньо швидко, інакше підіспіє охорона і схопить грабіжників. Тому забрати можна буде не з усіх повозок.
Коля, який грає, як і слід було очікувати, за ельфів, знає і кількість повозок у каравані N, і скільки золота у кожній повозці (у i-ій повозці знаходиться a_i золота), і максимальну кількість повозок k, яку його загін успіє обійти до прибуття охорони. Йому необхідно взнати максимальну кількість золота, яку він може отримати в результаті операції.
Вхідні дані
В первой строке заданы два целых числа N и k (1 ≤ k ≤ N ≤ 100000), определяющие размер каравана и максимальное число повозок, которые можно ограбить. Во второй строке задаются N целых чисел a_i, определяющие количество золота в повозках (0 ≤ a_i ≤ 10000).
Вихідні дані
У єдиному рядку виведіть найбільшу суму, яку може принести пограбування.