Qventin babanın oyunu#10219
Rayan və Ceyk kinoya və stolüstü oyunlara böyük maraq göstərirlər. Kinoteatrlar bağlı olduğundan, əylənmək üçün baba Kvintinin maraqlı bir oyununu tapıblar. Oyun aşağıdakı qaydalarla keçirilir:
Sahədə hüceyrə var, bunlar -dən -ə qədər nömrələnib.
Hər hüceyrədə bir tam ədəd yazılıb.
Oyunçu nömrəli hüceyrədən başlayır və yalnız irəli hərəkət edərək nömrəli hüceyrəyə çatmalıdır.
Sahənin sərhədlərindən kənara çıxmaq olmaz.
Oyunçu maksimum addım ata bilər. Yəni, nömrəli hüceyrədən istənilən x+1 və x+K (daxil olmaqla) nömrəli hüceyrəyə keçə bilər.
Oyunçunun nəticəsi — oyunda keçdiyi bütün hüceyrələrdəki ədədlərin cəminə bərabərdir.
Rayan qələbə qazanmağı çox sevir, buna görə də ən böyük mümkün nəticəni əldə etmək istəyir. Ceyk isə tam əksinə olaraq ən kiçik mümkün nəticəni əldə etməyə çalışır.
Onlar maraqlanırlar ki, tamamilə əks strategiyalardan istifadə etdikdə nəticələrinin fərqi nə olacaq. Onlara bu dəyəri tapmağa kömək edin.
Birinci sətirdə iki natural ədəd — və .İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n — hər bir hüceyrədə yazılmış ədədlər (birincidən başlayaraq). 1 \le N, K \le 10^6, -10^9 \le a_i \le 10^9.
Çıxışa bir tam ədəd yazın — sualın cavabı: Rayan və Ceykin nəticələrinin fərqini.
Nümunə 1
Nümunə 2