Lýsing á verkefni

Á borði liggja $N$ brjóstsykursmolar í einni láréttri röð, númeraðir í röð frá vinstri til hægri frá $1$ til $N$. Ljúffengleiki brjóstsykursmola $i$ ($1 \le i \le N$) er $A_i$.

JOI-kun ákvað að velja nokkra af þessum $N$ brjóstsykursmolum og borða þá.

Hins vegar, til að borða ekki of mikið af brjóstsykri, borðar hann í mesta lagi $2$ mola úr hverjum $K$ samliggjandi brjóstsykursmolum. Með öðrum orðum, fyrir sérhvert $j$ ($1 \le j \le N - K + 1$), þá má fjöldi brjóstsykursmola sem hann borðar úr þeim $K$ samliggjandi molum frá mola $j$ til mola $j + K - 1$ vera í mesta lagi $2$.

Með þessu skilyrði vill JOI-kun hámarka heildarljúffengleika brjóstsykursmolanna sem hann borðar.

Gefinn ljúffengleiki allra $N$ brjóstsykursmolanna og $K$, skrifið forrit sem finnur hæsta mögulega gildi á heildarljúffengleika brjóstsykursmolanna sem JOI-kun borðar.

Takmarkanir

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($4$ stig) $N \le 20$.
2. ($19$ stig) $K \le 10$.
3. ($47$ stig) $N \le 300$.
4. ($30$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

N K
A_1 A_2 ... A_N

Úttak

Á staðalúttak skal skrifa út í $1$ línu hæsta mögulega gildi á heildarljúffengleika brjóstsykursmolanna sem JOI-kun borðar.

Dæmi

Sýnidæmi um inntak 1

5 4
1 3 2 4 3

Sýnidæmi um úttak 1

8

Þegar JOI-kun borðar mola $1$, mola $4$ og mola $5$ er heildarljúffengleikinn $8$.

Meðal þeirra leiða til að borða mola þannig að í mesta lagi $2$ molar séu borðaðir úr hverjum $4$ samliggjandi molum er engin með heildarljúffengleika $9$ eða meira, svo skrifað er út $8$.

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.

Sýnidæmi um inntak 2

6 3
3 7 1 5 6 4

Sýnidæmi um úttak 2

21

Þegar JOI-kun borðar mola $1$, mola $2$, mola $4$ og mola $5$ er heildarljúffengleikinn $21$.

Meðal þeirra leiða til að borða mola þannig að í mesta lagi $2$ molar séu borðaðir úr hverjum $3$ samliggjandi molum er engin með heildarljúffengleika $22$ eða meira, svo skrifað er út $21$.

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.

Sýnidæmi um inntak 3

5 2
3 3 2 2 1

Sýnidæmi um úttak 3

11

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.

Sýnidæmi um inntak 4

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

Sýnidæmi um úttak 4

4427122428

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.