Một bản đồ hình vuông kích thước ~N \times N~ được chia thành lưới các ô vuông, trong mỗi ô vuông có một số nguyên không âm thể hiện độ cao của ô vuông đó. Mỗi bước di chuyển trên bản đồ, một robot có khả năng nhảy cao ~D~ đơn vị đo đi được sang một trong ~4~ ô kề cạnh nếu chênh lệch độ cao của ô đang đứng và ô sẽ đến không quá ~D~.

Yêu cầu: Tìm số nguyên không âm ~D~ nhỏ nhất để robot có khả năng nhảy cao ~D~ xuất phát tại ô bất kì trên bản đồ có thể đi thăm ít nhất một nửa số ô của bản đồ (nếu tổng số ô của bản đồ là số lẻ thì một nửa được làm tròn lên).

Dữ liệu vào

Từ tệp văn bản ROBOT.INP gồm:

• Dòng thứ nhất chứa số nguyên ~N~ ~(1 \le N \le 500)~ là kích thước của bản đồ.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên không âm là độ cao của các ô trên dòng tương ứng. Các số có giá trị không quá ~10^9~, mỗi số cách nhau ít nhất một dấu cách.

Kết quả ra

Xuất ra tệp văn bản ROBOT.OUT số nguyên ~D~ như mô tả ở trên.

Ví dụ

ROBOT.INP

5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3

ROBOT.OUT

3

Giải thích

Trong ví dụ trên, robot có khả năng nhảy cao ~3~ có thể di chuyển giữa các ô có độ chênh lệch từ ~0~ đến ~3~. Do đó robot đi thăm tất cả các ô có độ cao ~0~ và ~3~, tổng số ô robot đã đến là ~16~ (hơn nửa tổng số ô trên bản đồ). Độ cao ~3~ cũng là giá trị nhỏ nhất tìm được thỏa mãn yêu cầu trên.