Задача ВсОШ "Сумма минимумов"

Условие
У Саши есть блокнот, состоящий из n листочков, пронумерованных от 1 до n. На i-м листочке написано целое число ai. Аня собирается разорвать блокнот на k частей, для этого она выбирает k-1 число 1 ≤ r1 < r2 < … < rk-1 < n и разрывает блокнот так, что листки с 1 по r1-й оказываются в первой части, листки с (r1+1)-го по r2-й оказываются во второй части, и т.д., последняя k-я часть содержит листки с (rk-1 + 1)-го по n-й. После того, как Аня разорвет блокнот, Саша найдет минимальное число в каждой из получившихся частей и сложит их. Аня хочет разорвать блокнот таким образом, чтобы получившаяся сумма была как можно больше. Помогите ей выбрать способ разорвать блокнот, чтобы максимизировать сумму минимальных значений.

Имя входного файла: summin.in
Имя выходного файла: summin.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Формат входного файла
Первая строка ввода содержит два числа: n и k (2≤k≤n≤300).
Вторая строка содержит n целых чисел: a1, a2, …, an (1≤ai≤109).

Формат выходного файла
На первой строке выведите максимальное значение суммы, которое удастся достичь Ане.
На второй строке выведите значения r1, r2, …, rk-1, которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

Пример

summin.in

10 5

1 10 2 8 9 3 5 4 7 6

summin.out

27

3 4 5 8

Пояснение к примеру
В приведенном примере Аня разорвала блокнот на части [1, 10, 2], [8], [9], [3, 5, 4] и [7, 6].
Искомая сумма равна 1 + 8 + 9 + 3 + 6 = 27.

0