Задача №112527. Реклама(3)
Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня. И при этом обязательно транслировать ровно два рекламных ролика в день.
Фирма собрала информацию о количестве покупателей в каждый момент некоторого дня. Менеджер по рекламе предположил, что и на следующий день покупатели будут приходить и уходить ровно в те же моменты времени.
Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик.
Ролик длится ровно одну единицу времени. Для каждого момента времени известно количество покупателей, находящихся в магазине в этот момент. Между концом первой рекламы и началом следующей должна пройти как минимум К - 1 единица времени.
Первая строка содержит два числа N (моментов времени) и K (время совершения покупки одним покупателем). Гарантируется, что N > K. ( N, K ≤ 200 000 ). Во второй строке содержится N чисел a i — количество покупателей в момент времени i . ( 0 ≤ a i ≤ 2 000 000 000 ).
Выведите единственное число — количество просмотревших рекламу покупателей.
5 2 3 5 1 4 2
9