Tehtävänanto

Pöydällä on $N$ karkkia yhdessä vaakasuorassa rivissä, ja ne on numeroitu vasemmalta oikealle luvuin $1$–$N$. Karkin $i$ ($1 \le i \le N$) herkullisuus on $A_i$.

JOI-kun päätti valita joitakin $N$ karkista ja syödä ne.

Jotta hän ei kuitenkaan söisi liikaa karkkeja, hän syö mistä tahansa $K$ peräkkäisestä karkista enintään $2$. Toisin sanoen jokaisella $j$ ($1 \le j \le N - K + 1$) karkista $j$ karkkiin $j + K - 1$ ulottuvien $K$ peräkkäisen karkin joukosta syötävien karkkien lukumäärän on oltava enintään $2$.

Tämän ehdon vallitessa JOI-kun haluaa maksimoida syömiensä karkkien herkullisuuksien summan.

Kun $N$ karkin herkullisuudet ja $K$ annetaan, kirjoita ohjelma, joka selvittää suurimman mahdollisen JOI-kunin syömien karkkien herkullisuuksien summan.

Rajoitukset

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($4$ pistettä) $N \le 20$.
2. ($19$ pistettä) $K \le 10$.
3. ($47$ pistettä) $N \le 300$.
4. ($30$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

N K
A_1 A_2 ... A_N

Tuloste

Tulosta vakiotulosteeseen $1$ riville JOI-kunin syömien karkkien herkullisuuksien summan suurin mahdollinen arvo.

Esimerkit

Esimerkkisyöte 1

5 4
1 3 2 4 3

Esimerkkituloste 1

8

Kun JOI-kun syö karkin $1$, karkin $4$ ja karkin $5$, herkullisuuksien summa on $8$.

Sellaisista syömistavoista, joissa mistä tahansa $4$ peräkkäisestä karkista syödään enintään $2$ karkkia, yhdessäkään herkullisuuksien summa ei ole $9$ tai enemmän, joten tulostetaan $8$.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkkisyöte 2

6 3
3 7 1 5 6 4

Esimerkkituloste 2

21

Kun JOI-kun syö karkin $1$, karkin $2$, karkin $4$ ja karkin $5$, herkullisuuksien summa on $21$.

Sellaisista syömistavoista, joissa mistä tahansa $3$ peräkkäisestä karkista syödään enintään $2$ karkkia, yhdessäkään herkullisuuksien summa ei ole $22$ tai enemmän, joten tulostetaan $21$.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkkisyöte 3

5 2
3 3 2 2 1

Esimerkkituloste 3

11

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkkisyöte 4

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

Esimerkkituloste 4

4427122428

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.