Hoàng có N chiếc ly với dung tích vô hạn, và mỗi ly chứa một ít nước. Anh ấy muốn uống hết toàn bộ lượng nước, nhưng lại không muốn phải uống từ quá K ly.

Hoàng có thể đổ toàn bộ lượng nước từ ly này sang ly khác. Tuy nhiên, cần cân nhắc kỹ việc chọn ly để đổ, bởi không phải ly nào cũng ở gần Hoàng như nhau. Cụ thể, công sức cần bỏ ra để đổ nước từ ly được đánh số i sang ly được đánh số j là C_ij.

Hãy giúp Hoàng tìm một cách đổ nước sao cho cuối cùng chỉ còn tối đa K ly có nước, đồng thời tổng lượng công sức bỏ ra là ít nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương N, K (1 ≤ K ≤ N ≤ 20).
• Tiếp theo là N dòng, mỗi dòng chứa N số nguyên dương C_ij (0 ≤ C_ij ≤ 10^5).
• Dòng thứ i, cột thứ j chứa giá trị C_ij. Đảm bảo rằng C_ii = 0. Nói đơn giản: Nếu bạn đổ nước từ ly số 3 sang… chính ly số 3, thì không tốn chi phí gì cả (vì thực chất chẳng làm gì).

Output

• In ra tổng lượng công sức tối thiểu cần bỏ ra.

Sample input

3 3
0 1 1
1 0 1
1 1 0

Sạmple output

0

Giải thích Hoàng 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 input

3 2
0 1 1
1 0 1
1 1 0

Sạmple output

1

Giải thích Hoàng 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 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

Sạmple output

5

Giải thích Để Hoàng đạt được tổng là 5, anh ấy cần đổ từ ly 4 vào ly 3 (công sức tốn 1), rồi từ →3→5 (công sức tốn 2), và cuối cùng từ →1→5 (công sức tốn 2). Tổng cộng là 1+2+2=5 công sức.