Có ~n~ cái cốc được đánh số từ ~1~ đến ~n~, mỗi cốc chứa một lượng nước (không giới hạn dung tích).
An muốn uống hết số nước trong tất cả các cốc nhưng chỉ muốn uống ở đúng ~k~ cốc.
Để làm được điều này, An cần rót nước từ các cốc dư sang các cốc thiếu sao cho cuối cùng chỉ còn đúng ~k~ cốc chứa nước.

Khi rót nước từ cốc ~i~ sang cốc ~j~, An cần một lượng thời gian:

$$ C_{i,j} $$

và nếu ~i = j~ thì ~C_{i,i} = 0~.
Mỗi phép rót nước được xem là độc lập và không ảnh hưởng đến nhau.

Nhiệm vụ: chọn ra đúng ~k~ cốc để giữ lại nước, sau đó rót toàn bộ nước từ các cốc còn lại sang các cốc đã chọn sao cho tổng thời gian rót là nhỏ nhất.

Yêu cầu

Cho:

• ~n~ cốc,
• ~k~ cốc cần giữ lại nước,
• Ma trận thời gian ~C_{i,j}~ với ~C_{i,j}~ là thời gian rót nước từ cốc ~i~ sang cốc ~j~,

hãy tìm tổng thời gian nhỏ nhất để dồn toàn bộ nước vào đúng ~k~ cốc.

Dữ liệu

• Dòng 1: hai số nguyên ~n, k~ (~1 \le k \le n \le 20~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~n~ số nguyên ~C_{i,j}~ (~0 \le C_{i,j} \le 10^5~), là thời gian rót nước từ cốc ~i~ sang cốc ~j~.

Kết quả

• Một số nguyên duy nhất: tổng thời gian tối thiểu để dồn nước vào đúng ~k~ cốc.

Ví dụ

Ví dụ 1

Input

4 2
0 8 49 23
7 0 30 22
44 28 0 23
9 40 15 0

Output

16

Giải thích ví dụ

An chọn giữ lại cốc ~1~ và cốc ~3~.
Cách rót tối ưu:

• Rót nước từ cốc ~2 \to 1~: tốn ~7~
• Rót nước từ cốc ~4 \to 1~: tốn ~9~

Tổng thời gian:
$$ 7 + 9 = 16. $$

Không có lựa chọn nào khác cho tổng thời gian nhỏ hơn.

Chấm điểm