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

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100000.

1 ≤ d ≤ N − 1.

1 ≤ a_i ≤ 10⁹.

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

7 4
3 4 5 6 7 1 2

10

5 3
1 2 3 4 1

5