eolymp
bolt
Try our new interface for solving problems
Məsələlər

Караваны

Караваны

\textit{"Здраствуйте. Я, Кирилл. Хотел бы чтобы вы сделали игру, 3Д-экшон суть такова... Пользователь может играть лесными эльфами, охраной дворца и злодеем. И если пользователь играет эльфами то эльфы в лесу, домики деревяные набигают солдаты дворца и злодеи. Можно грабить корованы... \[skipped\] P.S. Я джва года хочу такую игру.} \textit{Письмо в компанию по разработке игр MiST land} Ну и конечно же Петя не мог при разработке не учесть пожеланий мирового геймерского сообщества, поэтому в его игре можно "набегать" и "грабить корованы". Караван состоит из повозок, в каждой из которых находится определенное количество золота. Ограбление можно начать с любой повозки, продвигаясь далее к следующей или предыдущей и забирая золото, которое находится в них. Всю операцию нужно провести достаточно быстро, иначе подоспеет охрана и схватит грабителей. Поэтому забрать можно будет не из всех повозок. Коля, играющий, как и следовало ожидать, за эльфов, знает и количество повозок в караване \textbf{N}, и сколько золота в каждой повозке (в \textbf{i}-ой повозке находится \textbf{a_i} золота), и максимальное количество повозок \textbf{k}, которое его отряд успеет обойти до прибытия охраны. Ему необходимо узнать максимальное количество золота, которое он может получить в результате операции. \InputFile В первой строке заданы два целых числа \textbf{N} и \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{N} ≤ \textbf{100000}), определяющие размер каравана и максимальное число повозок, которые можно ограбить. Во второй строке задаются \textbf{N} целых чисел \textbf{a_i}, определяющие количество золота в повозках (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{10000}). \OutputFile В единственной строке выведите наибольшую сумму, которую может принести ограбление.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
7 3
3 2 1 2 3 2 1
Çıxış verilənləri #1
7
Müəllif Виталий Неспирный
Mənbə Зимняя школа, Харьков 2011, День 6