Những hộp kẹo

Bé Hải An có $n$ hộp kẹo, hộp thứ $i$ có $a_i$ chiếc. Bé muốn dồn các hộp sao cho tổng số hộp còn lại không quá $k$. Mỗi bước dồn hai hộp $i,j$ là lấy hết số kẹo từ hộp $i$ đổ sang hộp $j$ với chi phí là $c_{ij}$.

Sau khi bị đổ hết kẹo sang hộp khác, hộp $i$ trở thành hộp rỗng và không còn được tính là hộp còn lại; hộp $j$ nhận kẹo phải là một hộp chưa bị đổ đi (vẫn còn kẹo). Một hộp có thể nhận kẹo nhiều lần, và một hộp đã nhận kẹo vẫn có thể được đổ tiếp sang hộp khác. Số kẹo $a_i$ không ảnh hưởng đến chi phí nên không được cho trong dữ liệu vào.

Yêu cầu: Tìm chi phí ít nhất để dồn $n$ hộp kẹo sao cho còn lại không quá $k$ hộp.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n,k$ ($1\le k\le n$).
• $n$ dòng sau, dòng thứ $i+1$ chứa $n$ số nguyên không âm $c_{i1},c_{i2},\dots ,c_{in}$. Trong đó, $c_{ij}$ ($i\ne j$) là chi phí để đổ hết kẹo từ hộp thứ $i$ sang hộp thứ $j$, $0\le c_{ij}\le {10}^5$. Có thể $c_{ij}\ne c_{ji}$. Các số $c_{ii}$ luôn bằng $0$ và không có ý nghĩa.

Dữ liệu ra

In ra một số nguyên không âm duy nhất là chi phí ít nhất để dồn $n$ hộp kẹo.

Ràng buộc

• $1\le k\le n\le 20$.
• $0\le c_{ij}\le {10}^5$, $c_{ii}=0$.

Subtasks

• $60\%$ số test có $n\le 10$.
• $40\%$ số test còn lại có $10<n\le 20$.

Ví dụ