diệu

Bé Thảo có \(n\) cái cốc, điều đặc biệt là những chiếc cốc này có dung tích vô hạn (đổ vào đó bao nhiêu nước cũng được) nên bé Thảo gọi chúng là những chiếc cốc diệu kỳ. Bé Thảo rất thích chơi với chúng và mẹ bé đã nghĩ ra một trò chơi thú vị để đố bé. Ban đầu mẹ bé đổ vào \(n\) cốc này mỗi cốc một ít nước. Mẹ nói Thảo phải uống hết tất cả số nước mà mẹ vừa đổ ra nhưng không được uống quá \(k\) cốc. Nghĩa là bé có thể đổ toàn bộ nước của một cốc \(i\) sang một cốc \(j\) khác. Cứ thực hiện như vậy để cuối cùng còn không nhiều hơn \(k\) cái cốc có nước và bé có thể uống. Chi phí để đổ nước từ cốc thứ \(i\) sang cốc thứ \(j\) kí hiệu là \(c_{ij}\).

Yêu cầu: Hãy tìm cách đổ nước theo quy luật trên để tổng chi phí cần phải bỏ ra là ít nhất.

Dữ liệu vào:

+ Dòng đầu chứa 2 số nguyên dương \(n,\ k\) \((1\ \leq \ k\ \leq \ n\ \leq \ 20)\).

+ \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên dương thể hiện mảng chi phí \(c_{i,j}\) \((0\ \leq \ c_{ij}\ \leq \ 10^{5})\), trong đó dòng thứ\(\ i + 1\) cột thứ \(j\) chứa giá trị \(c_{ij}\). Dĩ nhiên là \(c_{ii} = 0\).

Kết quả:

+ Đưa ra chi phí nhỏ nhất để có thể thực hiện yêu cầu trên.

Ví dụ:

Giải thích:

• Ví dụ 1: không cần đổ nước ở cốc nào sang cốc khác.

• Ví dụ 2: có thể đổ nước từ cốc 4 sang 3 (chi phí=1), sau đó đổ từ cốc 3 sang 5 (chi phí=2), và cuối cùng đổ từ 1 sang 5 (chi phí = 2). Tổng chi phí là 1 + 2 + 2= 5

Ràng buộc:

• Subtask 1: 40% số điểm ứng với \(n\ \leq \ 10\).

• Subtask 2: 60% số điểm ứng với \(10\ < \ n\ \leq \ 20\).