Matcom Online Grader

Fito se ha mudado a una importante finca y está recorriendo los terrenos para decidir qué sembrar. Después de mucho explorar, Fito ha decidido plantar $K$ cultivos en un surco de $N$ metros. A Fito le gusta mucho el orden y por tanto en cada metro de surco solo plantará un tipo de cultivo, incluso los metros del mismo cultivo siempre estarán consecutivos. Cuando Fito empieza a planificar la distribución que desea, se percata de que la altura del suelo en el surco es demasiado irregular. Decide entonces que para hacer más fácil la futura etapa de recolección, todos los cultivos de un mismo tipo han de quedar a la misma altura. Para alcanzar esta meta Fito puede cavar un metro de tierra o aumentar en un metro la altura del surco y ambas operaciones le toman una unidad de esfuerzo. El objetivo concreto es obtener un surco dividido en $K$ regiones consecutivas, cada una con la misma altura y empleando para la tarea, la menor cantidad de esfuerzo. Inicialmente el surco puede tener huecos y lomas, por lo que la altura de cada metro puede ser negativa o positiva.

La primera línea de la entrada tiene dos enteros $N$ y $K$ que representan respectivamente la cantidad de metros de surco $(1 \leq N \leq 1000)$ y la cantidad de cultivos $(1 \leq K \leq 25)$. Le siguen $N$ líneas y la i-ésima de ellas contiene al entero $Hi (-10000 \leq Hi \leq 10000)$, que indica la altura inicial del i-ésimo metro de surco.