תיאור הבעיה

על השולחן מונחות $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

דוגמת קלט זו מקיימת את המגבלות של כל תתי-המשימות.