Máy kéo

Cho một lưới $N\times N$ biểu diễn độ cao địa hình. Chi phí di chuyển của máy kéo từ ô này sang ô liền kề bằng hiệu tuyệt đối độ cao giữa hai ô.

Với chi phí tối đa $D$, máy kéo chỉ có thể di chuyển qua các cạnh có hiệu độ cao $\le D$. Cần tìm chi phí tối thiểu $D$ để máy kéo có thể đi đến ít nhất $\lceil N^2/2\rceil$ ô (bắt đầu từ bất kỳ ô nào).

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng $i+1$ (với $1\le i\le N$): $N$ số nguyên cách nhau bởi dấu cách — độ cao của các ô trong hàng $i$

Dữ liệu ra

• Một số nguyên duy nhất: chi phí tối thiểu $D$

Ràng buộc

• $1\le N\le 500$
• $0\le h_{ij}\le {10}^6$

Ví dụ