У Миши есть массив из n целых чисел. Он хочет выбрать k различных подотрезков в нем так, чтобы для каждого элемента массива нашелся хотя бы один выбранный отрезок, который его содержит.
При этом Миша хочет, чтобы если просуммировать числа на каждом отрезке, а затем просуммировать получившиеся суммы, то итоговая сумма оказалась максимальна.
Выходные данные
Выведите одно целое число — максимальную сумму сумм чисел на отрезках, которую можно достичь, выбрав k отрезков так, что каждый элемент был покрыт хотя бы одним отрезком.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
6 -4 -10 -4 7
|
11
|