Descripción del problema

Sobre un escritorio hay $N$ caramelos alineados en una fila horizontal, numerados del $1$ al $N$ de izquierda a derecha. La delicia del caramelo $i$ ($1 \le i \le N$) es $A_i$.

JOI-kun decidió elegir algunos de los $N$ caramelos y comérselos.

Sin embargo, para no comer demasiados caramelos, de cualesquiera $K$ caramelos consecutivos, se come a lo sumo $2$. Es decir, para todo $j$ ($1 \le j \le N - K + 1$), de entre los $K$ caramelos consecutivos desde el caramelo $j$ hasta el caramelo $j + K - 1$, la cantidad de caramelos que se come debe ser de $2$ o menos.

Bajo esta condición, JOI-kun quiere que la suma de las delicias de los caramelos que se come sea lo mayor posible.

Dada la delicia de los $N$ caramelos y el valor de $K$, escribe un programa para hallar el valor máximo de la suma de las delicias de los caramelos que se come JOI-kun.

Restricciones

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Todos los valores de entrada son números enteros.

Subtareas

1. ($4$ puntos) $N \le 20$.
2. ($19$ puntos) $K \le 10$.
3. ($47$ puntos) $N \le 300$.
4. ($30$ puntos) Sin restricciones adicionales.

Entrada

La entrada se proporciona desde la entrada estándar en el siguiente formato:

N K
A_1 A_2 ... A_N

Salida

En la salida estándar, imprime en $1$ línea el valor máximo de la suma de las delicias de los caramelos que se come JOI-kun.

Ejemplos de entrada y salida

Ejemplo de entrada 1

5 4
1 3 2 4 3

Ejemplo de salida 1

8

Cuando JOI-kun se come el caramelo $1$, el caramelo $4$ y el caramelo $5$, la suma de las delicias es $8$.

De entre las maneras de comer caramelos en las que para cualesquiera $4$ caramelos consecutivos se comen a lo sumo $2$ caramelos, no existe ninguna cuya suma de delicias sea $9$ o más, por lo que se imprime $8$.

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de entrada 2

6 3
3 7 1 5 6 4

Ejemplo de salida 2

21

Cuando JOI-kun se come el caramelo $1$, el caramelo $2$, el caramelo $4$ y el caramelo $5$, la suma de las delicias es $21$.

De entre las maneras de comer caramelos en las que para cualesquiera $3$ caramelos consecutivos se comen a lo sumo $2$ caramelos, no existe ninguna cuya suma de delicias sea $22$ o más, por lo que se imprime $21$.

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de entrada 3

5 2
3 3 2 2 1

Ejemplo de salida 3

11

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de entrada 4

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

Ejemplo de salida 4

4427122428

Este ejemplo de entrada satisface las restricciones de todas las subtareas.