Совсем недавно вышел новый ITone 6, и Юра очень захотел себе его купить. К сожалению, денег у него не хватало, поэтому Юра устроился работать программистом. На работе Юра столкнулся со следующей задачей:
Задана последовательность из n чисел p1, p2, ..., pn. Нужно выбрать k пар целых чисел:
[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m), так чтобы сумма 
была как можно больше. Помогите Юре справиться с этим заданием.
Выходные данные
В единственной строке выведите целое число — максимальное значение суммы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 1
1 2 3 4 5
|
9
|
|
2
|
7 1 3
2 10 7 18 5 33 0
|
61
|