Bé Hải An có ~n~ hộp kẹo, hộp thứ ~i~ có ~a_i~ chiếc. Bé muốn dồn các hộp sao cho tổng số hộp còn lại không quá ~k~. Mỗi bước dồn hai hộp ~i, j~ là lấy hết số kẹo 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 kẹo.

Input

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

• ~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}~ ~(1 \le j < n)~ là chi phí để dồn hộp thứ ~i~ và hộp thứ ~j~, ~0 \le c_{ij} \le 10^5~.

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 kẹo.

Scoring

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

Notes

Chuyển hết số kẹo từ hộp ~4~ sang hộp ~3~ (chi phí ~1~), sau đó chuyển hết số kẹo từ hộp ~3~ sang hộp ~5~ (chi phí ~2~). Cuối cùng, chuyển kẹo từ hộp ~1~ sang hộp ~5~ (chi phí ~2~). Tổng chi phí là ~1+2+2~.