Mislav có ~N~ ly với vô hạn thể tích, và mỗi ly chứa một ít nước. Mislav muốn uống hết toàn bộ lượng nước, nhưng anh ấy không muốn uống từ quá ~K~ ly. Mislav có thể đổ hết nước từ ly này sang ly khác. Tuy nhiên, cần cân nhắc trong việc chọn ly, bởi vì không phải ly nào cũng cách Mislav cùng khoảng cách. Chính xác hơn, lượng nỗ lực tốn để đổ nước từ ly được đánh dấu ~i~ vào ly được đánh dấu ~j~ là ~C_{ij}~. Hãy giúp Mislav tìm một cách đổ nước vào ly sao cho tổng lượng nỗ lực là ít nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên dương ~N, K~ ~( 1 \leq K \leq N \leq 20)~.

~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên dương ~C_{ij}~ ~(0 \leq C_{ij} \leq 10^5)~.

Dòng thứ ~i~, cột thứ ~j~ chứ giá trị ~C_{ij}~. Đảm bảo ~C_{ii} = 0~.

Output

In ra tổng lượng nỗ lực ít nhất có thể.

Sample 1

Input

3 3
0 1 1
1 0 1
1 1 0

Output

0

Giải thích

Mislav không cần đổ nước từ ly này vào ly khác vì anh ấy có thể uống tối đa ~3~ ly.

Sample 2

Input

3 2
0 1 1
1 0 1
1 1 0

Output

1

Giải thích

Mislav cần phải đổ nước từ một ly này (không quan trọng ly nào) vào ly khác để chỉ còn ~2~ ly.

Sample 3

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

Output

5

Giải thích

Để Mislav đạt được tổng là ~5~, anh ấy cần đổ từ ly ~4~ vào ly ~3~ (nỗ lực tốn ~1~), rồi từ ~3 \rightarrow 5~ (nỗ lực tốn ~2~), và cuối cùng từ ~1 \rightarrow 5~ (nỗ lực tốn ~2~). Tổng cộng là ~1 + 2 + 2 = 5~ nỗ lực.

Scoring

• ~4~ test đầu có ~N \leq 10~.
• ~6~ test còn lại không có ràng buộc gì thêm.