Siendo un admirador de la arquitectura contemporánea, el Granjero Juan ha construido un nuevo establo en la forma de un círculo perfecto. Adentro, el establo consiste de un anillo de ~n~ habitaciones, numeradas en sentido horario ~1...n~ alrededor del perímetro del establo. Cada habitación tiene puertas a sus dos habitaciones vecinas y también una puerta abriendo al exterior del establo.

El Granjero Juan quiere que exactamente ~r_i~ vacas terminen en la habitación ~i~. Para arrear a las vacas en el establo de una manera ordenada, él planea abrir ~k~ puertas exteriores, permitiendo que las vacas entren únicamente a través de esas puertas. Cada vaca entonces camina en sentido horario a través de las habitaciones hasta llegar a un destino apropiado. El Granjero Juan quiere abrir las puertas exteriores que causarán que sus vacas caminen colectivamente una cantidad mínima de distancia después de entrar al establo (ellas pueden inicialmente hacer fila en cualquiera de las ~k~ puertas abiertas; esto no contribuye a la distancia total en cuestión). Por favor, determine la distancia mínima total que sus vacas necesitan caminar, si él elige las mejores ~k~ de tales puertas a abrir.

Entrada

La primera línea de entrada contiene ~n~ y ~k~. Cada una de las restantes ~n~ líneas contiene ~r_1...r_n~.

Salida

Por favor, escriba la cantidad mínima de distancia que las vacas necesitan recorrer.

Restricciones

• ~3 \leq n \leq 1,000~
• ~1 \leq r_i \leq 1,000,000~
• ~1 \leq k \leq 7~

Ejemplo de Entrada

6 2
2
5
4
2
6
2

Ejemplo de Salida

14

El Granjero Juan puede abrir las puertas 2 y 5. 11 vacas entran por la puerta 2 y caminan una distancia total de 8 para ir a las habitaciones 2, 3 y 4. 10 vacas entran por la puerta 5 y caminan una distancia total de 6 para ir a las habitaciones 5, 6 y 1.

USACO 2016 February Contest, Platinum Problem 3. Circular Barn.