Máy kéo

Cho bản đồ $N\times N$ ô vuông, mỗi ô $(i,j)$ có độ cao $h_{i,j}$. Một chiếc máy kéo có thể di chuyển giữa hai ô kề nhau (ngang hoặc dọc) nếu chênh lệch độ cao giữa chúng không vượt quá $K$.

Tìm giá trị $K$ nhỏ nhất sao cho từ một ô nào đó, máy kéo có thể đến được ít nhất $\lceil N^2/2\rceil$ ô khác nhau.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$.
• $N$ dòng tiếp: Mỗi dòng chứa $N$ số nguyên biểu diễn độ cao các ô trong hàng đó.

Dữ liệu ra

Một số nguyên — giá trị $K$ nhỏ nhất thỏa mãn yêu cầu.

Ràng buộc

• $1\le N\le 500$
• $0\le h_{i,j}\le {10}^6$

Ví dụ