Гра дідуся Квентіна#10219

Гра дідуся Квентіна

2 секунди

128 мегабайтів

Середня

Раян і Джейк обожнюють кіно та настільні ігри. Але кінотеатри зачинені, а розважатись хочеться. Тому хлопці знайшли у дідуся Квентина цікаву гру з наступними правилами:

Є поле, що складається з $N$ клітинок, розташованих у ряд та пронумерованих від $1$ до $N$ .
На кожній клітинці записано ціле число.
Гравець починає з клітинки номер $1$ і має дістатися до клітинки номер $N$ , рухаючись лише вперед.
Виходити за межі поля заборонено.
Гравець може робити кроки не більше ніж на $K$ клітинок. Тобто з клітинки $x$ можна потрапити у будь-яку клітинку між $x + 1$ x+1 та $x + K$ x+K включно.
Результат гравця — сума всіх чисел, написаних у клітинках, на які він наступить протягом гри.

Раян обожнює перемагати, тому хоче отримати найбільший можливий результат. Джейк, навпаки, цінує сам процес гри та хоче отримати найменший можливий результат.

Хлопці зацікавилися, якою буде різниця між їхніми результатами, якщо вони використовують абсолютно протилежні стратегії. Допоможіть їм знайти цю різницю.

Вхідні дані

У першому рядку задано два натуральних числа: $N$ та $K$ .У другому рядку містяться $N$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n — числа у клітинках, починаючи з першої. $1 \leq N, K \leq 1 0^{6}$ 1 \le N, K \le 10^6, $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу: різниця між результатами Раяна та Джейка.

Приклади

Приклад 1

Приклад 2