Bờm và những chiếc ly

Bờm có N ly với vô hạn thể tích, và mỗi ly chứa một ít nước. Bờm 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. Bờm 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 Bờm cùng khoảng cách. Chính xác hơn, thời gian để đổ nước từ ly được đánh dấu i vào ly được đánh dấu j là Cij. Hãy giúp Bờm tìm một cách đổ nước vào ly sao cho tổng thời gian là ít nhất có thể.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương N, K ~(1 ≤ K ≤ N ≤ 20)~.
• N dòng tiếp theo, mỗi dòng chứa N số nguyên dương ~Cij~ ~(0 ≤ Cij ≤ 10^5)~.
• Dòng thứ i, cột thứ j chứa giá trị ~Cij~. Đảm bảo ~Cii~ = 0.

Kết quả:

• In ra tổng thời gian ít nhất có thể.

Ví dụ:

WATER.INP:

3 3
0 1 1
1 0 1
1 1 0

WATER.OUT:

0

WATER.INP:

3 2
0 1 1
1 0 1
1 1 0

WATER.OUT:

1

WATER.INP:

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

WATER.OUT:

5

Giải thích:

Với test cuối, để Bờm đạt được tổng thời gian là 5, anh ấy cần đổ:

• Từ ly 4 vào ly 3 (thời gian 1)
• Từ ly 3 vào ly 5 (thời gian 2)
• Từ ly 1 vào ly 5 (thời gian 2)

Tổng cộng: 1 + 2 + 2 = 5

Chú ý:

• 40% số test có N ≤ 10