Финансовый аналитик компании "Хлебосушки" анализирует прибыль компании на протяжении N месяцев. Аналитику поставили задачу найти интервал длиной не менее K месяцев с максимальной прибылью. Месяцы имеют сквозную нумерацию, начиная с 1 (с месяца открытия компании).
Вы - ведущий программист компании. Вам дали задачу написать программу, которая бы находила максимальную прибыль в непрерывном интервале длиной не менее K месяцев.
Формат входных данных
Первая строка содержит натуральное число
N (1 <
N ≤ 1 000 000) – количество месяцев существования компании и натуральное число
K (1 <
K <
N) – минимально допустимый интервал. В каждой из следующих
N строк находится одно целое число
profiti, не превышающее по модулю 10 000 000: прибыль компании за
iй месяц.
Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее
K месяцев. Гарантируется, что ответ к задаче не превышает 10
9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
-10
-1
30
10
-5
|
39
|