El pequeño Mislav tiene ~N~ vasos de volumen infinito y cada vaso contiene algo de agua. Mislav quiere tomar toda el agua, pero él no quiere tomar de más de ~K~ vasos. Lo que Mislav puede hacer es vaciar el volumen total de agua de un vaso a otro.

Desafortunadamente, le importa a Mislav que vaso elija, debido a que no todos los vasos están a la misma distancia de él. Más precisamente, la cantidad de esfuerzo que le cuesta vaciar el agua del vaso ~i~ al vaso ~j~ está denotada por ~C_{ij}~.

Ayude a Mislav a encontrar el orden de vaciar agua de un vaso a otro de tal manera que la suma de todos los esfuerzos sea mínima.

Entrada

La primera línea de la entrada contiene los enteros ~N, K~ ~(1 \leq K \leq N \leq 20)~. Las siguientes ~N~ líneas contienen ~N~ enteros ~C_{ij}~ ~(0 \leq C_{ij} \leq 10^8)~. La i-ésima fila y la j-ésima columna contiene el valor ~C_{ij}~. Se cumplirá que cada ~C_{ii}~ es 0.

Salida

Dé el esfuerzo mínimo necesario para que Mislav obtenga su objetivo.

Ejemplo #1 de Entrada

3 3
0 1 1
1 0 1
1 1 0

Ejemplo #1 de Salida

0

Ejemplo #2 de Entrada

3 2
0 1 1
1 0 1
1 1 0

Ejemplo #2 de Salida

1

Ejemplo #3 de Entrada

5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0

Ejemplo #3 de Salida

5

Aclaración del primer ejemplo: Mislav no necesita vaciar agua con el propósito de tomar de a lo más 3 vasos.

Aclaración del segundo ejemplo: Mislav debe vaciar agua de precisamente un vaso (no importa cual) en otro vaso con el propósito de quedarse únicamente con dos vasos de agua.

Aclaración del tercer ejemplo: Para que Mislav obtenga una solución mínima de 5, él puede vaciar agua del vaso 4 al 3 (esfuerzo 1), luego 3 → 5 (esfuerzo 2) y finalmente 1 → 5 (esfuerzo 2) en total, ~1+1+2 = 5~ cantidad de esfuerzo.