Cô Ban có ~n~ hộp kẹo và mỗi hộp có chứa 1 viên kẹo. Cô muốn dồn các hộp sao cho tổng số hộp còn lại (có chứa kẹo) là 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}~ cho trước (chú ý rằng không nhất thiết có ~c_{ij} = c_{ji}~). Yêu cầu đặt ra là tìm chi phí ít nhất để dồn ~n~ hộp kẹo theo yêu cầu.

Input

Dòng đầu chứa 2 số nguyên dương ~n,k.~

Trong ~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 đó, ~0 \le c_{ij} \le 10^5~ với ~1≤j \le n~ là chi phí để dồn hộp thứ ~i~ và hộp thứ ~j~, tất nhiên khi ~i=j~ thì ~c_{ij}=0.~

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

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 thích: 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 = 5~.

Subtasks:

• Sub1: 60% số test có ~n≤10~
• Sub2: 40% số test tiếp theo có ~10<n≤20.~</li>