C. Жорж ба ажил

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жорж саяхан гарсан шинэ хувилбар ITone 6-г худалдаж авахыг маш их хүсэж байна. Харамсалтай нь түүнд хангалттай мөнгө байсангүй, тиймээс тэр програмистаар ажиллахаар болов. Түүний ажил нь дараах асуудалтай тулгарлаа. $n$ бүхэл тоонуудтай $p_{1}, p_{2}, ..., p_{n}$ дараалал өгөгдсөн. Чи эдгээр бүхэл тоонуудаас $k$ хосуудыг сонгоно:

$[l_{1}, r_{1}], [l_{2}, r_{2}], ..., [l_{k}, r_{k}]$ $(1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} < ... < l_{k} ≤ r_{k} ≤ n; r_{i} - l_{i} + 1 = m), $

ийм аргаар нийлбэрийн утга боломжит хамгийн их байна. Даалгаврыг шийдвэрлэхэд нь Жоржд тусал.

Оролт

Эхний мөр нь $n$, $m$, $k$ $(1 ≤ (m × k) ≤ n ≤ 5000)$ гурван бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ бүхэл тоонууд $p_{1}, p_{2}, ..., p_{n}$ $(0 ≤ p_{i} ≤ 10^{9})$ агуулна.

Гаралт

Нийлбэрийн хамгийн их боломжит утгыг нэг мөрөнд хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
5 2 1
1 2 3 4 5
Гаралт
9
Оролт
7 1 3
2 10 7 18 5 33 0
Гаралт
61
Сэтгэгдлүүдийг ачааллаж байна...