Optimal Water Transfer

Mislav has \(N\) glasses, numbered from \(1\) to \(N\). Each glass initially contains some water. He wants to pour water from some glasses into others such that in the end at most \(K\) glasses contain water. When water is poured from glass \(i\) to glass \(j\), it costs \(C_{i,j}\). Note that pouring water from one glass into another that already contains water reduces the number of glasses with water by one.

If we choose a set \(S\) (with \(1 \le |S| \le K\)) of glasses to remain with water, then for every glass \(i \notin S\) we must pour its water into one of the glasses in \(S\) at a cost of \(\min_{j \in S}\, C_{i,j}\). The goal is to choose such a set \(S\) to minimize the total cost:

[ \text{Total Cost} = \sum_{i \notin S} \min_{j \in S} C_{i,j}. ]

Compute the minimum total cost required.

inputFormat

The first line contains two integers \(N\) and \(K\) (the number of glasses and the maximum number of glasses that may retain water).

The following \(N\) lines each contain \(N\) integers. The \(j^{th}\) integer in the \(i^{th}\) line represents \(C_{i,j}\), the cost of pouring water from glass \(i\) to glass \(j\).

It is guaranteed that \(C_{i,i} = 0\) for all \(1 \le i \le N\).

outputFormat

Output a single integer: the minimum total cost required to achieve at most \(K\) glasses with water.

sample

3 2
0 1 2
1 0 3
2 3 0

1