An có \(n\) hộp đựng đĩa CD, được đánh số từ 1 đến \(n\). An muốn dồn các hộp sao cho tổng số hộp còn lại không quá \(k\) hộp. 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}\).

Yêu cầu: Tìm chi phí ít nhất để dồn \(n\) hộp đĩa CD?

Input

• Dòng đầu chứa 2 số nguyên dương ~n, k (1 ≤ k ≤ n ≤ 20);

• \(n\) dòng sau, dòng thứ i+1 chứa n số nguyên không âm \(c_{i1},c_i2,…,c_{in}\). Trong đó, \(c_{ij} (1 ≤ j < n) \) 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í chi phí ít nhất để dồn \(n\) hộp đĩa.

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