27271번 - Сумма минимумов 스페셜 저지다국어

문제

У Саши есть блокнот, состоящий из $n$ листочков, пронумерованных от 1 до $n$. На $i$-м листочке написано целое число $a_i$.

Аня собирается разорвать блокнот на $k$ частей, для этого она выбирает $k-1$ число 1ドル \le r_1 < r_2 < \ldots < r_{k-1} < n$ и разрывает блокнот так, что листки с 1 по $r_1$-й оказываются в первой части, листки с $(r_1+1)$-го по $r_2$-й оказываются во второй части, и т.д., последняя $k$-я часть содержит листки с $(r_{k-1}+1)$-го по $n$-й.

После того, как Аня разорвет блокнот, Саша найдет минимальное число в каждой из получившихся частей и сложит их. Аня хочет разорвать блокнот таким образом, чтобы получившаяся сумма была как можно больше. Помогите ей выбрать способ разорвать блокнот, чтобы максимизировать сумму минимальных значений.

입력

Первая строка ввода содержит два числа: $n$ и $k$ (2ドル \le k \le n \le 300$). Вторая строка содержит $n$ целых чисел: $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 10^9$).

출력

На первой строке выведите максимальное значение суммы, которое удастся достичь Ане. На второй строке выведите значения $r_1, r_2, \ldots, r_{k-1},ドル которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

제한

노트

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