Гра дiдуся Квентiна
Раян i Джейк обожнують кiно та настiльнi iгри. Але кiнотеарти зачиненi, а розважатись хочеться. Тому хлопцi знайшли у дiдуся Квентiна цiкаву гру з наступними правилами:
Є поле що складається з N клiтинок розташованих в ряд, та пронумерованих вiд 1 до N .
На конжнiй клiтинцi записано цiле число.
Гравець повинен дiйти зi стартової клiтинки (номер 1) до фiнiшної (номер N ) рухаючись тiльки вперед.
Виходити за межi поля заборонено.
Гравець може ходити з максимальним кроком K. Iншими словами, з клiники номер x гравець може потрапити в будь-яку клiтинку мiж x + 1 та x + k включно.
Результат гри для гравця - сума всiх чисел записаних в клiтинках на якi вiн наступить протягом гри.
Раян обожнує перемагати, тому хоче отримати найбiльший можливий результат.Джейк - навпаки. Вiн надає перевагу процесу, тому хоче отримати найменший можливий результат.
Хлопцi зацiкавились, якою буде рiзниця їх результатiв при абсолютно протилежних стратегiях гри. Допоможiть їм.
Вхідні дані
В першому рядку два натуральних числа - N та K.В другому рядку N цiлих чисел a[1] , a[2] , ..., a[n] - числа записанi в кожнiй клiтинцi пiдряд починаючи з першої. 1 ≤ N, K ≤ 10^6, −10^9 ≤ a[i] ≤ 10^9
Вихідні дані
Одне цiле число - вiдповiдь на задачу. Рiзниця мiж результатами Раяна та Джейка.