Descrizione del problema

Su una scrivania ci sono $N$ caramelle allineate in una fila orizzontale, numerate da $1$ a $N$ da sinistra a destra. La bontà della caramella $i$ ($1 \le i \le N$) è $A_i$.

JOI-kun ha deciso di scegliere alcune delle $N$ caramelle e mangiarle.

Tuttavia, per non mangiare troppe caramelle, per qualsiasi gruppo di $K$ caramelle consecutive ne mangia al massimo $2$. In altre parole, per ogni $j$ ($1 \le j \le N - K + 1$), tra le $K$ caramelle consecutive dalla caramella $j$ alla caramella $j + K - 1$, il numero di caramelle mangiate deve essere al massimo $2$.

Rispettando questa condizione, JOI-kun vuole massimizzare la somma delle bontà delle caramelle che mangia.

Data la bontà delle $N$ caramelle e il valore di $K$, scrivi un programma per trovare il valore massimo della somma delle bontà delle caramelle mangiate da JOI-kun.

Vincoli

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Tutti i valori di input sono numeri interi.

Sottoproblemi

1. ($4$ punti) $N \le 20$.
2. ($19$ punti) $K \le 10$.
3. ($47$ punti) $N \le 300$.
4. ($30$ punti) Nessun vincolo aggiuntivo.

Dati di input

L'input viene fornito dallo standard input nel seguente formato:

N K
A_1 A_2 ... A_N

Dati di output

Sullo standard output, stampa in $1$ riga il valore massimo della somma delle bontà delle caramelle mangiate da JOI-kun.

Esempi di input/output

Input di esempio 1

5 4
1 3 2 4 3

Output di esempio 1

8

Quando JOI-kun mangia la caramella $1$, la caramella $4$ e la caramella $5$, la somma delle bontà è $8$.

Tra i modi di mangiare le caramelle tali che per qualsiasi gruppo di $4$ caramelle consecutive se ne mangino al massimo $2$, non ne esiste alcuno con una somma delle bontà pari o superiore a $9$, quindi si stampa $8$.

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.

Input di esempio 2

6 3
3 7 1 5 6 4

Output di esempio 2

21

Quando JOI-kun mangia la caramella $1$, la caramella $2$, la caramella $4$ e la caramella $5$, la somma delle bontà è $21$.

Tra i modi di mangiare le caramelle tali che per qualsiasi gruppo di $3$ caramelle consecutive se ne mangino al massimo $2$, non ne esiste alcuno con una somma delle bontà pari o superiore a $22$, quindi si stampa $21$.

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.

Input di esempio 3

5 2
3 3 2 2 1

Output di esempio 3

11

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.

Input di esempio 4

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

Output di esempio 4

4427122428

Questo esempio di input soddisfa i vincoli di tutti i sottoproblemi.