Олонлог эгзэ сургуулийн сурагчид спортын баярын үеэр сургуулийн хашаанд байрлах тойрог замаар гүйж оноо цуглуулдаг тэмцээнд оролцож байна.

Зам нь тойрог хэлбэртэй, өөрөөр хэлбэл:

• Сүүлчийн хэсгээс эхний хэсэг рүү шууд шилжиж орох боломжтой N хэсгээс бүрдэх болно

Замын хэсэг бүр дээр:

• Зарим нь оноо нэмнэ (эерэг тоо)
• Зарим нь оноо хасна (сөрөг тоо)

Та дараалсан хэсгийг сонгож гүйх боломжтой:

• Хэсгүүд нь дараалсан байх ёстой
• Гэхдээ тойрог тул төгсгөлөөс эхлэл рүү үргэлжилэх юм
• Гэхдээ та хамгийн ихдээ K ширхэг хэсгээр дамжин гүйж харгалзах хэсгийн оноог авах боломжтой

Таны зорилго:

Цуглуулж болох хамгийн их боломжит онооны нийлбэрийг олох явдал юм.

Оролт:

N K

a1 a2 a3 ... aN

Гаралт:

sum length

Хязгаарлалтууд:

• \(1 ≤ N,K ≤ 10^5\)
• \(-10^9 ≤ a[i] ≤ 10^9\)

Дэд бодлого

Жишээ:

Оролт-1

5
5 -3 5

Гаралт-1

10