Есептің шарты

Үстел үстінде көлденең бір қатарға $N$ кәмпит тізіліп қойылған, олар солдан оңға қарай ретімен $1$-ден $N$-ге дейін нөмірленген. $i$-ші кәмпиттің ($1 \le i \le N$) дәмділігі — $A_i$.

Джой-кун осы $N$ кәмпиттің ішінен бірнешеуін таңдап жеуді ұйғарды.

Алайда кәмпитті тым көп жеп қоймау үшін, кез келген қатар орналасқан $K$ кәмпиттің ішінен ол әрі кеткенде $2$ кәмпит қана жейді. Басқаша айтқанда, кез келген $j$ ($1 \le j \le N - K + 1$) үшін $j$-ші кәмпиттен $j + K - 1$-ші кәмпитке дейінгі қатар орналасқан $K$ кәмпиттің ішінде желінетін кәмпиттердің саны $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

Бұл кіріс мысалы барлық ішкі есептердің шектеулерін қанағаттандырады.