รายละเอียดปัญหา

บนโต๊ะมีลูกกวาด $N$ เม็ดวางเรียงกันเป็นแถวแนวนอน โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ ตามลำดับจากซ้ายไปขวา ความอร่อยของลูกกวาดเม็ดที่ $i$ ($1 \le i \le N$) คือ $A_i$

JOIคุงตัดสินใจเลือกลูกกวาดบางเม็ดจากลูกกวาด $N$ เม็ดมากิน

อย่างไรก็ตาม เพื่อไม่ให้กินลูกกวาดมากเกินไป สำหรับลูกกวาด $K$ เม็ดที่เรียงติดกันใดๆ เขาจะกินลูกกวาดในกลุ่มนั้นอย่างมากที่สุด $2$ เม็ดเท่านั้น กล่าวคือ สำหรับทุกๆ $j$ ($1 \le j \le N - K + 1$) ในบรรดาลูกกวาด $K$ เม็ดที่เรียงติดกันตั้งแต่ลูกกวาดเม็ดที่ $j$ ถึงลูกกวาดเม็ดที่ $j + K - 1$ จำนวนลูกกวาดที่กินจะต้องไม่เกิน $2$ เม็ด

ภายใต้เงื่อนไขนี้ JOIคุงต้องการให้ผลรวมความอร่อยของลูกกวาดที่เขากินมีค่ามากที่สุดเท่าที่จะเป็นไปได้

เมื่อกำหนดความอร่อยของลูกกวาด $N$ เม็ด และค่า $K$ มาให้ จงเขียนโปรแกรมเพื่อหาค่าสูงสุดของผลรวมความอร่อยของลูกกวาดที่ JOIคุงกิน

ข้อจำกัด

• $2 \le K \le N \le 3\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

งานย่อย (Subtasks)

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$ บรรทัด เป็นค่าสูงสุดของผลรวมความอร่อยของลูกกวาดที่ JOIคุงกิน

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

ตัวอย่างข้อมูลนำเข้า 1

5 4
1 3 2 4 3

ตัวอย่างข้อมูลส่งออก 1

8

เมื่อ JOIคุงกินลูกกวาดเม็ดที่ $1$, ลูกกวาดเม็ดที่ $4$ และลูกกวาดเม็ดที่ $5$ ผลรวมความอร่อยจะเป็น $8$

ในบรรดาวิธีการกินที่ทำให้ลูกกวาด $4$ เม็ดที่เรียงติดกันใดๆ มีจำนวนลูกกวาดที่กินไม่เกิน $2$ เม็ด ไม่มีวิธีใดที่ได้ผลรวมความอร่อยตั้งแต่ $9$ ขึ้นไป ดังนั้นจึงแสดงผลเป็น $8$

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยทั้งหมด

ตัวอย่างข้อมูลนำเข้า 2

6 3
3 7 1 5 6 4

ตัวอย่างข้อมูลส่งออก 2

21

เมื่อ JOIคุงกินลูกกวาดเม็ดที่ $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

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยทั้งหมด