Сумма максимумов всех окон длины k

Датчик нагрузки пишет n замеров. Для каждого окна из k подряд идущих замеров найдите максимум и выведите сумму этих максимумов по всем n − k + 1 окнам.

Ввод: в первой строке n и k (1 ≤ k ≤ n ≤ 2500), во второй n чисел (|aᵢ| ≤ 10⁹).

Вывод: одно число: сумма максимумов окон (может не поместиться в 32 бита).

Пример 1

Ввод:

8 3
1 3 -1 -3 5 3 6 7

Вывод:

29

Пример 2

Ввод:

3 1
-1 -2 -3

Вывод:

-6