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} ~.

Dữ liệu vào

• Dòng đầu chứa 2 số nguyên dương ~ n, k ~ ~ (1 ≤ k ≤ n ≤ 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_{ij} ~ ~ (0 ≤ c_{ij} ≤ 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.

Ràng buộc

• 40% số điểm ứng với ~ n ≤ 10 ~.
• 60% số điểm ứng với ~ 10 < n ≤ 20 ~.

Ví dụ:

Input 1

```3 3 0 1 1 1 0 1 1 1 0

```

Output 1

0 

Input 2

```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 2

5