Problembeskrivning

På ett skrivbord ligger $N$ godisbitar i en horisontell rad, numrerade i ordning från vänster till höger från $1$ till $N$. Godheten hos godisbit $i$ ($1 \le i \le N$) är $A_i$.

JOI-kun bestämde sig för att välja ut några av de $N$ godisbitarna och äta dem.

För att inte äta för mycket godis äter han dock högst $2$ godisbitar bland vilka $K$ på varandra följande godisbitar som helst. Med andra ord måste antalet godisbitar han äter bland de $K$ på varandra följande godisbitarna från godisbit $j$ till godisbit $j + K - 1$ vara högst $2$ för varje $j$ ($1 \le j \le N - K + 1$).

Under detta villkor vill JOI-kun göra den totala godheten hos de godisbitar han äter så stor som möjligt.

Givet godheten hos de $N$ godisbitarna samt $K$, skriv ett program som beräknar det maximala värdet på den totala godheten hos de godisbitar JOI-kun äter.

Begränsningar

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Alla indatavärden är heltal.

Deluppgifter

1. ($4$ poäng) $N \le 20$.
2. ($19$ poäng) $K \le 10$.
3. ($47$ poäng) $N \le 300$.
4. ($30$ poäng) Inga ytterligare begränsningar.

Indata

Indatan ges från standardindata i följande format:

N K
A_1 A_2 ... A_N

Utdata

Skriv ut på $1$ rad till standardutdata det maximala värdet på den totala godheten hos de godisbitar JOI-kun äter.

Exempel

Indataexempel 1

5 4
1 3 2 4 3

Utdataexempel 1

8

När JOI-kun äter godisbit $1$, godisbit $4$ och godisbit $5$ blir den totala godheten $8$.

Bland de sätt att äta godis där högst $2$ godisbitar äts bland vilka $4$ på varandra följande godisbitar som helst finns det inget med en total godhet på $9$ eller mer, så $8$ skrivs ut.

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Indataexempel 2

6 3
3 7 1 5 6 4

Utdataexempel 2

21

När JOI-kun äter godisbit $1$, godisbit $2$, godisbit $4$ och godisbit $5$ blir den totala godheten $21$.

Bland de sätt att äta godis där högst $2$ godisbitar äts bland vilka $3$ på varandra följande godisbitar som helst finns det inget med en total godhet på $22$ eller mer, så $21$ skrivs ut.

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Indataexempel 3

5 2
3 3 2 2 1

Utdataexempel 3

11

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Indataexempel 4

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

Utdataexempel 4

4427122428

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.