{"raw_statement":[{"iden":"statement","content":"Таня уже 4 года занимается олимпиадным программированием. Увы, в этом году её команда не прошла в полуфинальный этап соревнований, и поэтому Таня присутствует на нём в качестве зрителя и болеет за команду Андрея. \n\nВ основном зрителями являются тренеры и руководители команд. Многие тренеры проводят в своих вузах разные соревнования, и у них есть традиция — на полуфинале обмениваться друг с другом книжечками, посвящёнными этим соревнованиям. Тренер Тани не может присутствовать на полуфинале, и теперь у Тани есть бесконечное количество книжечек, которые её попросили передать другим тренерам. Конечно, нужно сказать, что Таня не смогла отказать тренеру в просьбе передать книжечки, что она очень хотела перепоручить это важное дело Андрею, и что Андрей (смог откосить) убедил Таню в том, что никого из тренеров он не сможет увидеть: ведь для тренеров и других зрителей организуются разные мероприятия, пока участники соревнований пишут контест. \n\nНа полуфинале запланировано n мероприятий для тренеров и других зрителей. Эти мероприятия пронумерованы от 1 до n в порядке времени проведения, при этом ни одно мероприятие не пересекается с каким-либо другим. На i-м мероприятии Таня может успеть раздать ai книжечек. Проблема в том, что Таня социофоб, и общение с тренерами (а тренеры не могут просто взять книжечку, а непременно хотят поговорить) для неё очень утомительное и тяжёлое дело. Поэтому, если Таня посетила некоторое мероприятие, после него она убегает в свой номер в гостинице и находится там как минимум в течение следующих k мероприятий. Ваша задача — определить максимальное количество книжечек, которое Таня сможет раздать.\n\nНа всякий случай уточним, что ни одно мероприятие не проходит у Тани в номере, так что пока она там находится, раздавать книжечки она не может.\n\nВ первой строке записаны целые числа n и k (1 ≤ n, k ≤ 2·105) — количество мероприятий для тренеров и зрителей и количество мероприятий, которые Таня пропускает, пока находится в своём номере, соответственно.\n\nВо второй строке записаны n целых чисел a1, a2, ..., an, где ai (1 ≤ ai ≤ 109) — количество книжечек, которые Таня может раздать на i-м мероприятии.\n\nВыведите единственное целое число — максимальное количество книжечек, которое сможет раздать Таня.\n\nПояснение к первому примеру.\n\nТане следует пойти на 2-е мероприятие, раздать там 4 книжечки, затем в течение 3-го мероприятия отдыхать в номере, а потом пойти на 4-е мероприятие и раздать там ещё 5 книжечек.\n\n"},{"iden":"входные данные","content":"В первой строке записаны целые числа n и k (1 ≤ n, k ≤ 2·105) — количество мероприятий для тренеров и зрителей и количество мероприятий, которые Таня пропускает, пока находится в своём номере, соответственно.Во второй строке записаны n целых чисел a1, a2, ..., an, где ai (1 ≤ ai ≤ 109) — количество книжечек, которые Таня может раздать на i-м мероприятии."},{"iden":"выходные данные","content":"Выведите единственное целое число — максимальное количество книжечек, которое сможет раздать Таня."},{"iden":"примеры","content":"Входные данные5 11 4 6 5 1Выходные данные9Входные данные3 21 2 3Выходные данные3"},{"iden":"примечание","content":"Пояснение к первому примеру.Тане следует пойти на 2-е мероприятие, раздать там 4 книжечки, затем в течение 3-го мероприятия отдыхать в номере, а потом пойти на 4-е мероприятие и раздать там ещё 5 книжечек."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ be the number of events and the minimum number of consecutive events Tanya must skip after attending one, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of booklets Tanya can distribute at event $ i $.\n\n**Constraints**  \n1. $ 1 \\leq n, k \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. If Tanya attends event $ i $, she cannot attend any event $ j $ such that $ i < j \\leq i + k $.\n\n**Objective**  \nMaximize the total number of booklets distributed:  \n$$\n\\max \\sum_{i \\in S} a_i\n$$  \nwhere $ S \\subseteq \\{1, 2, \\dots, n\\} $ is a subset of events such that for any two consecutive selected events $ i, j \\in S $ with $ i < j $, it holds that $ j \\geq i + k + 1 $.","simple_statement":"Tanya wants to give out booklets at events. She can attend an event and give out a[i] booklets, but after attending any event, she must rest for the next k events. Find the maximum number of booklets she can give out.","has_page_source":false}