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