Chia đồng cỏ

Cho một lưới $N\times N$ biểu diễn số bò trong mỗi ô. Bạn có thể dựng tối đa $K$ hàng rào, mỗi hàng rào là một đường thẳng đứng hoặc nằm ngang trải qua toàn bộ chiều ngang/dọc của lưới (không được cắt xuyên qua ô). Các hàng rào chia lưới thành nhiều khu vực hình chữ nhật.

Hãy chọn cách đặt tối đa $K$ hàng rào sao cho khu vực lớn nhất (tổng số bò trong khu vực) là nhỏ nhất có thể.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$
• Dòng $i+1$ (với $1\le i\le N$): $N$ số nguyên, là số bò trong mỗi ô của hàng $i$

Dữ liệu ra

• Một số nguyên duy nhất: giá trị nhỏ nhất của khu vực lớn nhất

Ràng buộc

• $2\le N\le 15$
• $1\le K\le 2N-2$
• $0\le$ số bò trong mỗi ô $\le 1000$

Ví dụ