F - Array

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Probablemente estás cansado de largos y aburridos enunciados de problemas, por esa razón este tiene uno bastante simple. 

Dado un array de $n$ enteros, debes seleccionar exactamente $k$ números en diferentes posiciones cuya suma sea mínima, pero esto no es todo, no pude haber dos elementos en posiciones consecutivas.

Input

La primera línea contiene dos enteros $n$ y $k$, $(1 \le n \le 100000, 1 \le k \le \frac{n+1}{2})$, indicando la longitud del array y la cantidad de posiciones a seleccionar. En la segunda línea aparecen $n$ enteros $a_i$ ($0 \le a_i \le 1000000000$) separados por espacio, indicando los valores en cada posición del array.

Output

En la primera línea imprima la menor suma posible que puede ser obtenida. Y en la segunda imprima $k$ enteros en orden creciente, siendo las posiciones que seleccionaste. De haber varias soluciones posibles, imprima cualquiera.

Sample test(s)

Input
4 2 6 2 1 2
Output
4 2 4