Problem description

Szu jest renomowanym szulerem, który specjalizuje się w okradaniu najbogatszych kasyn. Oszukał już kasyna o numerach 1, 2, …, N − K i szykuje się do kolejnych skoków. Jego genialne umiejętności sprawiają, że z łatwością omija systemy zabezpieczeń, jednak aby maksymalizować swoje zyski, musi zoptymalizować koszty podróży między celami swoich oszustw.

Przedsiębiorczy Szu zauważył, że koszt rocznego biletu PKP pomiędzy kasynami o indeksach i oraz j wynosi w_i, j. Niestety, PKP wszędzie ma kontrolerów i nie jest tak łatwo ich oszukać. Szu ze swoim problemem skierował się do Ciebie. Dla podanej rozpiski cen połączeń pomiędzy kasynami podaj koszt najtańszego planu, dzięki któremu możliwe jest przemieszczanie się pomiędzy każdą parą kasyn o indeksach N − K + 1, …, N.

Problem ten wygląda bardzo podobnie do zadań, które robiłeś na początku swojej ścieżki programistycznej. Czy tym razem podołasz i rozwiążesz zadanie na 100?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i K, oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę kasyn oraz liczbę wybranych celów. Każdy z kolejnych N wierszy zawiera po N liczb całkowitych. i-ty wiersz i j-ta kolumna zawiera liczbę w_i, j, która reprezentuje koszt rocznego biletu w PKP.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się jedna liczba całkowita, oznaczająca minimalny koszt planu podróży, dzięki któremu możliwe jest przemieszczenie się pomiędzy każdą parą kasyn o indeksach N − K + 1, …, N.

Ograniczenia

0 ≤ N ≤ 32, 0 ≤ K ≤ N, 0 ≤ w_i, j = w_j, i ≤ 1 000.

Podzadania

Przykład

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

3