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