Умова задачі

На столі в один горизонтальний ряд лежать $N$ цукерок, пронумерованих зліва направо від $1$ до $N$. Смачність цукерки $i$ ($1 \le i \le N$) дорівнює $A_i$.

Джой-кун вирішив вибрати кілька з цих $N$ цукерок і з'їсти їх.

Однак, щоб не з'їсти забагато цукерок, із будь-яких $K$ послідовних цукерок він з'їдає не більше ніж $2$. Іншими словами, для кожного $j$ ($1 \le j \le N - K + 1$) серед $K$ послідовних цукерок від цукерки $j$ до цукерки $j + K - 1$ кількість з'їдених цукерок має бути не більшою за $2$.

За цієї умови Джой-кун хоче максимізувати сумарну смачність з'їдених ним цукерок.

За заданою смачністю $N$ цукерок і числом $K$ напишіть програму, яка знайде максимальну можливу сумарну смачність цукерок, які з'їсть Джой-кун.

Обмеження

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Усі вхідні значення є цілими числами.

Підзадачі

1. ($4$ бали) $N \le 20$.
2. ($19$ балів) $K \le 10$.
3. ($47$ балів) $N \le 300$.
4. ($30$ балів) Додаткових обмежень немає.

Вхідні дані

Вхідні дані подаються зі стандартного потоку вводу в такому форматі:

N K
A_1 A_2 ... A_N

Вихідні дані

У стандартний потік виводу виведіть в $1$ рядку максимальну можливу сумарну смачність цукерок, з'їдених Джой-куном.

Приклади

Приклад вводу 1

5 4
1 3 2 4 3

Приклад виводу 1

8

Коли Джой-кун з'їдає цукерку $1$, цукерку $4$ та цукерку $5$, сумарна смачність дорівнює $8$.

Серед способів вибору цукерок, за яких із будь-яких $4$ послідовних цукерок з'їдається не більше ніж $2$, не існує жодного із сумарною смачністю $9$ або більше, тому виводимо $8$.

Цей приклад задовольняє обмеження всіх підзадач.

Приклад вводу 2

6 3
3 7 1 5 6 4

Приклад виводу 2

21

Коли Джой-кун з'їдає цукерку $1$, цукерку $2$, цукерку $4$ та цукерку $5$, сумарна смачність дорівнює $21$.

Серед способів вибору цукерок, за яких із будь-яких $3$ послідовних цукерок з'їдається не більше ніж $2$, не існує жодного із сумарною смачністю $22$ або більше, тому виводимо $21$.

Цей приклад задовольняє обмеження всіх підзадач.

Приклад вводу 3

5 2
3 3 2 2 1

Приклад виводу 3

11

Цей приклад задовольняє обмеження всіх підзадач.

Приклад вводу 4

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

Приклад виводу 4

4427122428

Цей приклад задовольняє обмеження всіх підзадач.