Énoncé du problème

Il y a $N$ bonbons alignés horizontalement sur un bureau, numérotés de $1$ à $N$ de gauche à droite. La saveur du bonbon $i$ ($1 \le i \le N$) est $A_i$.

JOI-kun a décidé de choisir certains de ces $N$ bonbons et de les manger.

Cependant, afin de ne pas manger trop de bonbons, parmi $K$ bonbons consécutifs quelconques, il n'en mange qu'au plus $2$. Autrement dit, pour tout $j$ ($1 \le j \le N - K + 1$), parmi les $K$ bonbons consécutifs allant du bonbon $j$ au bonbon $j + K - 1$, le nombre de bonbons mangés doit être inférieur ou égal à $2$.

Sous cette condition, JOI-kun souhaite maximiser la somme des saveurs des bonbons qu'il mange.

Étant donné la saveur des $N$ bonbons ainsi que $K$, écrivez un programme permettant de trouver la valeur maximale de la somme des saveurs des bonbons mangés par JOI-kun.

Contraintes

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

1. ($4$ points) $N \le 20$.
2. ($19$ points) $K \le 10$.
3. ($47$ points) $N \le 300$.
4. ($30$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est fournie depuis l'entrée standard sous le format suivant :

N K
A_1 A_2 ... A_N

Sortie

Sur la sortie standard, affichez sur $1$ ligne la valeur maximale de la somme des saveurs des bonbons mangés par JOI-kun.

Exemples d'entrée/sortie

Exemple d'entrée 1

5 4
1 3 2 4 3

Exemple de sortie 1

8

Lorsque JOI-kun mange le bonbon $1$, le bonbon $4$ et le bonbon $5$, la somme des saveurs est de $8$.

Parmi les façons de manger les bonbons telles qu'au plus $2$ bonbons soient mangés parmi $4$ bonbons consécutifs quelconques, il n'en existe aucune dont la somme des saveurs soit supérieure ou égale à $9$ ; on affiche donc $8$.

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple d'entrée 2

6 3
3 7 1 5 6 4

Exemple de sortie 2

21

Lorsque JOI-kun mange le bonbon $1$, le bonbon $2$, le bonbon $4$ et le bonbon $5$, la somme des saveurs est de $21$.

Parmi les façons de manger les bonbons telles qu'au plus $2$ bonbons soient mangés parmi $3$ bonbons consécutifs quelconques, il n'en existe aucune dont la somme des saveurs soit supérieure ou égale à $22$ ; on affiche donc $21$.

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple d'entrée 3

5 2
3 3 2 2 1

Exemple de sortie 3

11

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple d'entrée 4

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

Exemple de sortie 4

4427122428

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.