An có N cái cốc được gán nhãn lần lượt 1,2,…,Nvới dung tích không hạn chế và trong mỗi cốc đều có nước. An muốn uống hết số nước ở tất cả các cốc nhưng chỉ muốn uống ở đúng K cốc. Để có thể làm được như vậy, cậu ta phải rót nước từ cốc này sang cốc khác để chỉ còn đúng K cốc có nước. đề đặt ra với An là chọn cốc nào để rót nước sang cốc nào, bởi vì khoảng cách giữa các cốc là không bằng nhau. Cụ thể, An sẽ mất một lượng sức khi rót nước từ cốc i sang cốc jgọi nó là C_ij.

Yêu cầu: Giúp An tìm thứ tự rót nước từ cốc này sang cốc khác để tổng lượng sức cậu ấy bỏ ra là ít nhất. Thỏa mãn điều kiện, An có thể uống hết lượng nước chỉ trong K cốc.

Input:

Dòng 1 chứa hai số nguyên N,K (1≤K≤N≤20) N dòng sau, dòng thứ i chứa N số nguyên C_ij (0≤C_ij≤10^5) là lượng sức cần dùng khi rót nước từ cốcisang cốcj. Nếu i=j thì C_ij=0.

Output:

Ghi một số duy nhất là tổng lượng sức ít nhất cần sử dụng.

Sample Input:

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

Sample Output

5

Giới hạn

Có 40% số test ứng với 40% số điểm của bài có 1≤N≤10
Có 60% số test ứng với 60% số điểm của bài có1≤N≤20