Скользящая сумма — задача по программированию

Найдите максимальную сумму окна длины k, обновляя сумму при сдвиге.

Входные данные

В первой строке n. Во второй — n целых чисел a[i]. В третьей строке k, 1 ≤ k ≤ n.

Максимальная сумма.

1 ≤ n ≤ 100000; −10^9 ≤ a[i] ≤ 10^9.

Ввод:

text

5
2 -1 4 3 -8
2

Вывод:

text

Ввод:

text

1
-3
1

Вывод:

text

-3

Ограничения

Пример 1

Ввод:

text

5
2 -1 4 3 -8
2

text

Пример 2

Ввод:

text

1
-3
1

text

-3