Problembeskrivelse

På en pult ligger det $N$ drops på en vannrett rekke, nummerert i rekkefølge fra venstre mot høyre fra $1$ til $N$. Smaken på drops $i$ ($1 \le i \le N$) har verdien $A_i$.

JOI-kun bestemte seg for å velge ut noen av de $N$ dropsene og spise dem.

For ikke å spise for mange drops spiser han imidlertid høyst $2$ drops blant hvilke som helst $K$ påfølgende drops. Med andre ord må antallet drops han spiser blant de $K$ påfølgende dropsene fra drops $j$ til drops $j + K - 1$ være høyst $2$ for enhver $j$ ($1 \le j \le N - K + 1$).

Under denne betingelsen ønsker JOI-kun at den totale smaksverdien av dropsene han spiser skal bli så stor som mulig.

Gitt smaksverdiene til de $N$ dropsene og $K$, skriv et program som finner den maksimale totale smaksverdien av dropsene JOI-kun spiser.

Begrensninger

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Alle inndataverdier er heltall.

Deloppgaver

1. ($4$ poeng) $N \le 20$.
2. ($19$ poeng) $K \le 10$.
3. ($47$ poeng) $N \le 300$.
4. ($30$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndataen gis fra standard inndata i følgende format:

N K
A_1 A_2 ... A_N

Utdata

Til standard utdata skal du på $1$ linje skrive ut den maksimale totale smaksverdien av dropsene JOI-kun spiser.

Eksempler

Eksempelinndata 1

5 4
1 3 2 4 3

Eksempelutdata 1

8

Når JOI-kun spiser drops $1$, drops $4$ og drops $5$, blir den totale smaksverdien $8$.

Blant måtene å spise drops på der det spises høyst $2$ drops blant hvilke som helst $4$ påfølgende drops, finnes det ingen med en total smaksverdi på $9$ eller mer, så det skrives ut $8$.

Dette eksempelet oppfyller begrensningene for alle deloppgaver.

Eksempelinndata 2

6 3
3 7 1 5 6 4

Eksempelutdata 2

21

Når JOI-kun spiser drops $1$, drops $2$, drops $4$ og drops $5$, blir den totale smaksverdien $21$.

Blant måtene å spise drops på der det spises høyst $2$ drops blant hvilke som helst $3$ påfølgende drops, finnes det ingen med en total smaksverdi på $22$ eller mer, så det skrives ut $21$.

Dette eksempelet oppfyller begrensningene for alle deloppgaver.

Eksempelinndata 3

5 2
3 3 2 2 1

Eksempelutdata 3

11

Dette eksempelet oppfyller begrensningene for alle deloppgaver.

Eksempelinndata 4

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

Eksempelutdata 4

4427122428

Dette eksempelet oppfyller begrensningene for alle deloppgaver.