小红走矩阵
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定n \times n的矩阵,矩阵中的每个元素都是正整数,小红能当前位于左上角(1,1),每次可以从 (x, y) 走到 (x+1, y)(x, y+1)(x-1, y)(x, y-1),但不能走出矩阵。小红希望找到一条到右下角(n,n)的路径,定义路径权值为路径上经过的每个点的最大值,求所有路径中的最小路径权值。

输入描述:

第一行一个整数n,表示矩阵的大小。
接下来n行,每行n个整数,表示矩阵中的元素a_{ij}
1 \leq n \leq 500
1 \leq a_{ij} \leq 10^9

输出描述:

输出一个整数,表示所有路径中的最小路径权值。
示例1

输入

复制
3
3 2 1
6 5 4
9 8 7

输出

复制
7

说明

先一直往右走,再一直往下走,路径上的最大值为7。