Задача D. Деревья

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В одном маленьком государстве была красивая аллея, на которой росли разные деревья. Но однажды в государстве случился дефицит древесины, поэтому правительство решило срубить пару деревьев аллеи. При этом требуется, чтобы расстояние между деревьями было достаточно большим, чтобы не нарушать красоту аллеи.

Даны значения высот N деревьев аллеи. Требуется найти два дерева, сумма высот которых максимальна и при этом расстояние между ними не меньше d. Расстояние — это разница порядковых номеров деревьев.

Формат входного файла

Входной файл содержит целые числа N d, за которым следуют N целых чисел ai — высоты деревьев.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — максимальную сумму высот деревьев, расстояние между которыми не меньше d.

Ограничения

2 ≤ N ≤ 100000.

1 ≤ d ≤ N − 1.

1 ≤ ai ≤ 109.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 4
3 4 5 6 7 1 2
10
2
5 3
1 2 3 4 1
5

0.183s 0.098s 15