Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito se encuentra jugando con una secuencia de $n$ enteros no negativos. En el juego él tiene que particionar la secuencia en $k+1$ partes no vacías. Cada parte es una subsecuencia contigua de la secuencia inicial. Para obtener $k+1$ partes realiza el siguiente procedimiento $k$ veces:

• Selecciona una parte con más de un elemento (inicialmente tiene una parte -- la secuencia completa).
• La divide por una posición entre dos elementos para obtener dos nuevas partes no vacías.

Después de cada operación Fito obtiene una cantidad de puntos igual al producto de las sumas de cada una de las partes que crea en la operación. Tu misión es calcular la mayor cantidad total de puntos que Fito puede obtener en el juego.

Input

La primera línea contiene dos enteros $n$ y $k$ ($2 \le n \le 100000$, $1 \le k \le \min(n-1,200)$). En la segunda línea aparecen $n$ enteros $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^4$) -- la secuencia.

Output

En la primera línea de la salida imprima la mayor cantidad de puntos totales que Fito puede obtener. En la segunda líea imprima $k$ enteros entre $1$ y $n-1$ -- las posiciones por las que podría realizar una partición para lograr esos puntos. Si existe más de una solución imprima cualquiera.

Sample test(s)

Hints

Se pueden obtener $108$ puntos de la siguiente forma:

• Inicialmente se tiene la secuencia $(4,1,3,4,0,2,3)$ como una parte. Si particiona por la posición siguiente al tercer elemento se obtienen: $(4+1+3)\times(4+0+2+3)=72$ puntos.
• Tienes dos partes $(4,1,3)$ y $(4,0,2,3)$. Particiona por la posición siguiente al primer elemento y obtienes: $(4)\times(1+3)=16$ puntos.
• Tienes tres partes $(4)$, $(1,3)$, $(4,0,2,3)$. Particiona por la posición siguiente al quinto elemento y obtienes: $(4+0)\times(2+3)=20$ puntos.

Al final tienes $4$ partes $(4)$, $(1,3)$, $(4,0)$, $(2,3)$ y ganaste: $72+16+20=108$ puntos.