Paul tiene una empresa de catering y el negocio va viento en popa. La empresa cuenta con $k$ equipos de personal, cada uno a cargo de un conjunto de material de catering. Cada semana acepta $n$ solicitudes de catering para distintos eventos. Para cada solicitud envía un equipo con su material al lugar del evento. El equipo entrega la comida, instala el material y enseña al anfitrión cómo utilizarlo y servir la comida. Después del evento, el anfitrión se encarga de devolver el material a la empresa de Paul.

Imagen de Wikimedia Commons

Por desgracia, algunas semanas hay menos equipos que solicitudes, por lo que algunos deben atender más de un evento. En estos casos, la empresa no puede esperar a que el anfitrión devuelva el material y debe mantener al equipo en el lugar para trasladarlo a otro sitio. La empresa tiene una estimación precisa del coste de trasladar un conjunto de material desde cualquier lugar a cualquier otro. Dados estos costes, Paul quiere preparar un Advance Catering Map para atender las solicitudes minimizando el coste total de traslado del material (incluido el primer traslado), aunque eso suponga no utilizar todos los equipos disponibles. Paul necesita tu ayuda para escribir un programa que realice esta tarea. Las solicitudes están ordenadas de forma ascendente por la hora de los eventos y se eligen de modo que, para cualquier $i<j$, haya tiempo suficiente para transportar el material utilizado en la solicitud $i$-ésima al lugar de la solicitud $j$-ésima.

Entrada

La primera línea de la entrada contiene dos enteros $n$ ($1 \le n \le 100$) y $k$ ($1 \le k \le 100$), el número de solicitudes y el número de equipos de catering, respectivamente. A continuación hay $n$ líneas; la línea $i$-ésima contiene $n-i+1$ enteros entre $0$ y $1\,000\,000$, ambos inclusive. El número $j$-ésimo de la línea $i$-ésima es el coste de trasladar un conjunto de material del lugar $i$ al lugar $i+j$. La empresa está en el lugar $1$ y las $n$ solicitudes están en los lugares del $2$ al $n+1$.

Salida

Muestra el coste mínimo de traslado para atender todas las solicitudes. (Esta cantidad no incluye el coste de devolver el material a la empresa de catering.)

Ejemplos

Entrada 1

3 2
40 30 40
50 10
50

Salida 1

80

Entrada 2

3 2
10 10 10
20 21
21

Salida 2

40