Thầy có ~n~ hộp đựng đĩa CD, hộp thứ ~i~ có ~a_i~ chiếc đĩa CD. Thầy muốn dồn các hộp sao cho tổng số hộp còn lại không quá ~k~ chiếc. Mỗi lần dồn hai hộp ~i, j~ là lấy hết số đĩa CD từ hộp ~i~ sang hộp ~j~ với chi phí là ~c_{ij}~.

Câu hỏi thách thức của thầy An là: Tìm chi phí ít nhất để dồn ~n~ hộp đĩa CD?

Yêu cầu: Hãy giúp Yên tìm chi phí ít nhất để dồn ~n~ hộp đĩa CD sao cho tổng số hộp còn lại không quá ~k~ chiếc.

Input

• Dòng đầu chứa 2 số nguyên dương ~n, k~ (~1 \le k \le n \le 20~).
• ~n~ dòng sau, dòng thứ ~i + 1~ chứa ~n~ số nguyên không âm ~c_{i1}, c_{i2}, \dots, c_{in}~. Trong đó, ~c_{ij}~ (~0 \le c_{ij} \le 10^5~) là chi phí để dồn hộp thứ ~i~ và hộp thứ ~j~.

Output

• In ra một số nguyên không âm duy nhất là chi phí ít nhất để dồn ~n~ hộp đĩa CD.

Sample Input 1

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 1

5