Раян 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лих чисел a1 , a2 , ..., an - числа записанi в кожнiй клiтинцi пiдряд починаючи з першої. 1 ≤ N, K ≤ 106, −109 ≤ ai ≤ 109

Вихідні дані

Одне цiле число - вiдповiдь на задачу. Рiзниця мiж результатами Раяна та Джейка.