Después de la última debacle relacionada con el granero circular del granjero John, uno pensaría que ha aprendido la lección sobre la arquitectura no tradicional. Sin embargo, cree que todavía puede hacer que su granero circular (del problema anterior) funcione correctamente permitiendo que entren varias vacas en cada habitación. Recapitulando, el granero consiste en un anillo de ~n~ habitaciones, numeradas en el sentido de las agujas del reloj desde ~1...n~ alrededor del perímetro del granero ~(3 \leq n \leq 100)~. Cada habitación tiene puertas a sus dos habitaciones vecinas, y también una puerta que da al exterior del granero.

El GJ quiere que exactamente ~r_i~ vacas acaben en la sala ~i (1 \leq r_i \leq 10^6)~. Para introducir las vacas en el establo de forma ordenada, planea desbloquear ~k~ puertas exteriores ~(1 \leq k \leq 7)~, permitiendo que las vacas entren sólo por esas puertas. A continuación, cada vaca recorre las habitaciones en el sentido de las agujas del reloj hasta llegar a un destino adecuado. El GJ quiere desbloquear las puertas exteriores que harán que sus vacas caminen colectivamente una cantidad mínima de distancia total después de entrar en el establo (pueden alinearse inicialmente como quieran fuera de las ~k~ puertas desbloqueadas; esto no contribuye a la distancia total en cuestión). Por favor, determine la distancia total mínima que sus vacas tendrán que caminar, si elige las mejores ~k~ puertas para desbloquear.

Entrada

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

Salida

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

Ejemplo de Entrada

6 2
2
5
4
2
6
2

Ejemplo de Salida

14

El granjero John puede desbloquear las puertas 2 y 5. 11 vacas entran por la puerta 2 y caminan un total distancia de 8 para llegar a las habitaciones 2, 3 y 4. 10 vacas entran por la puerta 5 y caminan un distancia total de 6 para llegar a las habitaciones 5, 6 y 1.