Условие задачи

На столе в один горизонтальный ряд лежат $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

Этот пример удовлетворяет ограничениям всех подзадач.