/**
Se da un sir de n numere naturale pe int. n<=1000000
Se mai da un k. Sa gasim suma tuturor secventelor de lungime k.

n = 8 k = 3
2 3 4 1  6  7  8  2
    9 8 11 14 21 17
Varianta 1: Fac sume partiale apoi am expresii de forma S[i] - S[i-k]
Varianta 2: Fara sume partiale precalculate Fac suma primei secvente apoi s+=v[i]; s-=v[i-k];

Pentru fiecare secventa de lungime k, sa calculam minimul.

2 3 4 1  6  7  8  2
    2

    2 1  1  1  6  2


k = 5
2 6 1 5 3

minimul 1


k = 5
vine elementul 4
2 6 1 5 3 4 7 3 2 9 10
          X X X X X
2 9 10

1 1 1 3 2 9

Parcurgem sirul dat element cu element.
Tinem o structura cu elementele intalnite dar care mai au sens, adica care mai pot fi minime ele vreunei secvente de lungime k
care mai urmeaza.
Pentru asta, la intalnirea unui element nou procedam astfel
- daca el este mai mic decat elementul de la finalul structurii il elimina pe acesta deorece este mai bun decat el (mai mic)
facem asta in mod repetat
- cand elemenul curent ajunge mai mare decat cel de la finalul strucrurii il adaugam in aceasta deoarece el este
mai la dreapta decat cele din structura si la un moment dat, tot miscandu-ma la dreapta cele din fata nu vor mai conta.
- tinem in structura doar elemente la distanta maxim k de pozitia curenta. Pentru asta, la implementare vom pastra
in structura indici din sirul dat pentru ca astfel am acces si la valoare si la pozitie.
- deci, dupa ce elementul curent din vector actioneaza la finalul structurii cum am descris mai sus, verificam daca elementul
din farta structurii nu a ajuns prea de departe de final, caz in care il eliminam.
Observam ca mereu elementele structurii sunt in ordine crescatoare. Dar am aratat ca se gasesc coar dintre ultimele k
rezulta ca minimul secventei de lungime k terminata cu elementul curent din vector va fi mereu primul element al structurii.

Streuctura prezentata se numeste deque (double ended queue, coada cu 2 capete) deoarece facem operatii ca in stiva la ambele capete.
La ce am prezentat nu facem adaugare la capatul din fata.
In stl exista o structura preimplementata numita chiar deque.

Sa facem 2 implementarim una de mana, fara structura stl si una cu ea.
**/

#include <fstream>
#define DIM 5000001
using namespace std;

int v[DIM];
int d[DIM];
int n, p, u, i, k;
long long suma = 0;

int main () {
    ifstream fin ("deque.in");
    ofstream fout("deque.out");
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>v[i];

    p = 1; u = 1;
    d[1] = 1; /// indicele lui v[1]. Punem in deque primul element din sir.

    if (k == 1)
        suma = v[1]; /// secventa de lungime k = 1 formata din primul element

    for (i=2;i<=n;i++) {
        /// vine randul elementului v[i]
        while (p<=u && v[i] <= v[ d[ u ] ])
            u--;

        d[++u] = i;

        if (i - d[p] == k) /// mergea si >= k dar intrucat i merge din 1 in 1 intai se ajunge la distanta chiar k
            p++;

        /// din acest moment intre pozitiile p si u din d se afla indici din v ai unor elemente relevante pentru secventa curenta
        /// si urmatoarele, toate aflate la distanta maxim k de pozitia curenta i
        if (i >= k) {
            suma += v[ d[p] ];
        }

    }

    fout<<suma;
    /**
    Justificarea complexitatii este de la problemele cu stive, adica la fiecare pas dintre cei n se adauga la structura
    un element iar while-ul scoate doar din ce s-a adaugat, cei in total maxim n.
    Timp O(n)
    **/

    return 0;
}