Bơi trong mưa

Một cơn mưa hiếm có đang đổ xuống một khu vực được chia thành lưới \(n \times n\). Mỗi ô \((i,j)\) có cao độ \(a_{i,j}\). Mực nước bắt đầu dâng từ \(t=0\) và tăng đều theo thời gian; tại thời điểm \(t\), bạn chỉ có thể đứng ở những ô có \(a_{i,j} \le t\).

Bạn đang ở ô xuất phát \((1,1)\) và muốn tới ô đích \((n,n)\). Mỗi bước bạn có thể di chuyển sang một trong bốn ô kề trực tiếp (lên, xuống, trái, phải), miễn là ô đến không cao hơn mực nước hiện tại.

Hãy tìm thời điểm nhỏ nhất \(t\) sao cho tồn tại đường đi từ \((1,1)\) đến \((n,n)\) chỉ qua các ô có \(a_{i,j} \le t\).

Input

• Dòng đầu chứa số nguyên \(n\). (\(1 \le n \le 700\))
• Tiếp theo là \(n\) dòng, mỗi dòng \(n\) số nguyên \(a_{i,j}\). (\(a_{i,j} \le n^2\)).

Đề đảm bảo các giá trị \(a_{i,j}\) phân biệt.

Output

In ra một số nguyên: giá trị nhỏ nhất của \(t\) thỏa yêu cầu.

Scoring

• Subtask 1 (30 điểm): \(1 \le n \le 50\).
• Subtask 2 (70 điểm): Không có ràng buộc thêm.

Sample Input 1

5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6

Sample Output 1

16