وصف المسألة

توجد على المكتب $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

مثال الإدخال هذا يحقق قيود جميع المهام الفرعية.