물컵 비우기

미슬라브는 부피가 무한한 컵을 $N$개 가지고 있고, 각 컵에는 물이 조금씩 들어 있다. 미슬라브는 물을 모두 마시고 싶지만, 컵을 $K$개보다 많이 쓰고 싶지는 않다. 미슬라브가 할 수 있는 일은 한 컵에 든 물을 전부 다른 컵으로 옮겨 붓는 것뿐이다.

컵마다 미슬라브에게서 떨어진 거리가 달라서 어느 컵을 고르는지가 중요하다. $i$번 컵의 물을 $j$번 컵으로 옮기는 데 드는 힘은 $C_{ij}$이다.

물이 남아 있는 컵이 $K$개 이하가 되도록 물을 옮길 때, 드는 힘의 합의 최솟값을 구하여라.

첫째 줄에 정수 $N$과 $K$가 주어진다. ($1 \le K \le N \le 20$)

다음 $N$개 줄에는 정수가 $N$개씩 주어진다. $i$번째 줄의 $j$번째 수가 $C_{ij}$이다. ($0 \le C_{ij} \le 100000$) 모든 $i$에 대해 $C_{ii} = 0$이다.

미슬라브가 목표를 이루는 데 드는 힘의 합의 최솟값을 한 줄에 출력한다.

물이 든 컵이 처음부터 $K$개 이하이면 물을 옮길 필요가 없고, 답은 0이다.

물은 여러 컵을 거쳐 갈 수 있다. $i$번 컵의 물을 $j$번 컵으로 옮긴 뒤, $j$번 컵의 물을 다시 $k$번 컵으로 옮겨도 된다.