En una calle hay ~n~ casas, numeradas del ~1,2,\dots,n~. La distancia entre las casas ~a~ y ~b~ es ~|a-b|~. Se conoce el número de niños en cada casa.

La tarea consiste en ubicar ~k~ escuelas de forma que cada escuela se encuentre en una casa. Luego, cada niño va a la escuela más cercana. ¿Cuál es la distancia mínima total que recorren los niños caminando si se actúa de forma óptima?

Entrada

La primera línea de entrada contiene dos enteros, ~n~ y ~k~: el número de casas y el número de escuelas. Las casas están numeradas del ~1,2\dots,n~. A continuación, se introducen ~n~ enteros, ~c_1,c_2,\dots,c_n~: el número de niños en cada casa.

Salida

Imprime la distancia mínima total.

Restricciones

• ~1 \leq k \leq n \leq 3000~
• ~1 \leq c_i \leq 10^9~

Ejemplo de Entrada

6 2
2 7 1 4 6 4

Ejemplo de Salida

11

Explicación: Las casas 2 y 5 tendrán escuelas.