You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

某探险队需要穿越一个古老的迷宫，以获取隐藏在迷宫深处的宝藏。迷宫由 $n \times m$ 个相同的石室组成，每个石室与相邻的四个石室之间有通道相连。在第 $n$ 行的 $m$ 个石室中藏有 $m$ 把钥匙，必须收集全部钥匙才能打开宝藏室的大门。而第 $1$ 行的 $m$ 个石室是迷宫的入口，探险队可以从任意入口进入。

除了第 $1$ 行和第 $n$ 行的石室外，其他每个石室都布有古老的机关，会对闯入者造成一定的伤害。第 $i$ 行第 $j$ 列的石室造成的伤害值为 $p_{i,j}$（第 $1$ 行和第 $n$ 行的 $p$ 值为 $0$，即入口和钥匙所在石室没有伤害）。

探险队可以派出任意多名队员，从任意入口进入迷宫，但必须确保每把钥匙都被至少一名队员拿到。单个队员受到的伤害为其所走路径上所有石室伤害值的最大值，而整个探险队的总伤害为所有队员伤害值中的最大值。探险队希望精心规划路线，使得总伤害最小。

输入格式

第一行有两个整数 $n, m$，表示迷宫的大小。
接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $p_{i,j}$。

输出格式

输出一个整数，表示探险队能够达成目标的最小总伤害。

4 2
0 0 
3 5 
2 4 
0 0

3

说明/提示

• $50\%$ 的数据，$n,m \leq 100$；
• $100\%$ 的数据，$n,m \leq 1000$，$p_{i,j} \leq 1000$。