Trang trại của Farmer John được chia thành một lưới vuông gồm \(N \times N\) đồng cỏ (\(2 \le N \le 15\)). Hiện tại, có một hàng rào bao quanh bên ngoài trang trại, nhưng bò có thể tự do di chuyển từ đồng cỏ này sang đồng cỏ khác.

Farmer John đã quyết định xây hàng rào để ngăn cách những con bò với nhau. Do các quy định về quy hoạch, mỗi hàng rào phải là một đường ngang hoặc dọc chạy xuyên suốt toàn bộ trang trại và không được đi qua bất kỳ đồng cỏ nào. Farmer John chỉ có đủ tiền để xây nhiều nhất \(K\) hàng rào (\(1 \le K \le 2N - 2\)).

Farmer John muốn xây các hàng rào sao cho số bò trong nhóm lớn nhất được tạo thành là nhỏ nhất (hai con bò thuộc cùng một nhóm nếu chúng có thể đi tới nhau mà không phải đi xuyên qua bất kỳ hàng rào nào). Biết số bò hiện có trong mỗi đồng cỏ, hãy giúp Farmer John tính số bò trong nhóm lớn nhất nếu ông xây hàng rào một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số mô tả số bò trong từng đồng cỏ của một hàng trên trang trại. Mỗi đồng cỏ có ít nhất 0 và nhiều nhất 1000 con bò.

Dữ liệu ra

In ra số bò nhỏ nhất có thể của nhóm lớn nhất.

Ví dụ

3 2
1 1 2
1 1 2
2 2 4

4

Nguồn

USACO 2013 February Contest, Gold — Problem 1: Partitioning the Farm

Tác giả đề: Brian Dean, 2013.