Олонлог эгзэ сургуулийн "Бүтээлч долоо хоног" болж байна. Сурагчид өдөр бүр янз бүрийн үйл ажиллагаанд оролцож оноо цуглуулдаг. Гэхдээ энэ удаа багш дараах стратегийн дүрэм тавьжээ:

Та:

• яг K удаа үйл ажиллагаанд оролцоно
• Оролцох бүрдээ дараалсан хэдэн өдөр сонгоно
• Сонгосон хэсгүүд хоорондоо давхцахгүй

Нэмэлт нөхцөл (хүндрүүлсэн хэсэг)

• Та хоосон хэсэг сонгож болохгүй
• Сонгосон хэсэг бүр дор хаяж 1 өдөртэй
• Сонгосон хэсгүүдийн хооронд дор хаяж 1 өдөр алгассан байх ёстой
• Өөрөөр хэлбэл хоёр хэсэг залгаа байж болохгүй

Таны зорилго

• Яг K ширхэг, давхцахгүй, хоорондоо залгаагүй дараалсан өдрүүдийг сонгож, нийт онооны нийлбэрийг хамгийн их болгох явдал юм

Оролт:

Эхний мөрөнд хоёр бүхэл тоо өгөгдөнө: N K

Дараагийн мөрөнд N ширхэг бүхэл тоо:

a1 a2 a3 ... aN

• N — өдрийн тоо
• K — сонгох хэсгийн тоо
• ai — i дахь өдрийн оноо

Гаралт:

хамгийн их боломжит нийлбэр

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

• \(1 ≤ N ≤ 100000\)
• \(1 ≤ K ≤ 10\)
• \(-1000 ≤ ai ≤ 1000\)

Дэд бодлого

Жишээ:

Оролт-1

6 2
1 2 -1 2 -3 2

Гаралт-1

5

Тайлбар

Боломжит сонголтууд:

[1 2] = 3 (алгасна) [2] = 2

Нийлбэр = 5

-️ [1 2] ба [2 -1 2] зэрэг нь давхцаж байгаа тул болохгүй

• Хоёр хэсэг залгаа байж болохгүй

Оролт-2

5 2
5 -1 5 -1 5

Гаралт-2

10

Тайлбар-2

Зөв сонголт:

[5] (1-р өдөр) (алгасна) [5] (3-р өдөр)

• Нийлбэр = 10
• [5] ба [5] (дараалсан байвал) болохгүй

Оролт-3

4 1
-2 -3 -1 -5

Гаралт-3

-1

Тайлбар

K = 1 тул хамгийн их утгатай ганц хэсгийг авна → -1