U629961 焦头烂额的日奈委员长
题目背景
由于美食研究部的众人绑架了枫香，所以今天的歌赫娜由朱莉提供。
但是由于某些众所周知的原因，今天的午饭不仅无法正常开饭，为师的大可爱还需要处理这些活蹦乱跳冒着绿色粘液的午饭，将枫香救出来!
题目描述
为师的日奈大可爱需要在的 \(n \times m\) 的歌赫娜餐厅中围剿这些活蹦乱跳的午饭，她现在在餐厅的 \((x_1,y_1)\) 处，但由于其重量太大且移动速度极其缓慢，因此将其看作不动的点，则 \(a_{i,j} > 0\)，其余点则没有这些午餐，则 \(a_{i,j} = 0\)。
为师的日奈大可爱聪明精干，跑一格只需要一个单位时间，收拾一份午饭只需要 \(a_{i,j}\) 单位个时间。
难缠的午饭会在日奈收拾过离开后便会恢复。
现在美食研究会的晴奈等人将枫香放置在某个没有午餐的点 \((hx,hy)\) 上，由泉把守，使得枫香无法移动。
已知，日奈在到达枫香的位置后便能将她救下(无需消耗额外时间，即日奈到达枫香所在格后枫香下一时刻便可以自行走路)，但是日奈会选择追击美食研究会等人，所以之后的路需要枫香自己走。
枫香跑一格需要一个单位时间，且无力清理午饭，她需要自行跑到 \((x_2,y_2)\) 处坐上伊吕波的虎丸号撤离。
设日奈出发的时刻为 \(0\)。
本题求枫香最快在哪一个时刻 \(t\) 能够坐上虎丸号撤离。
输入格式
共 \(n + 4\) 行。
第一行，两个正整数 \(n,m\)。
第二行，两个正整数 \(x_1,y_1\)。
第三行，两个正整数 \(x_2,y_2\)。
第四行，两个正整数 \(hx,hy\)。
接下来 \(n\) 行，每行 \(m\) 个正整数，每个数是 \(a_{i,j}\)。
输出格式
共一行。
输出一个正整数 \(t\)。
输入输出样例 #1
输入 #1
5 5
1 2
5 4
1 4
0 0 10 0 10
10 0 1 0 10
10 0 10 0 0
10 0 10 10 0
10 0 0 0 0
输出 #1
11
说明/提示
对于 \(100\%\) 的数据。
\(n,m \le 1 \times 10 ^3\)。
\(1 \le x_1,x_2,hx \le n\)。
\(1 \le y_1,y_2,hy \le m\)。
\(0 \le a_{i,j} \le 1 \times 10 ^ 9\)。
# U629961 焦头烂额的日奈委员长## 题目背景由于美食研究部的众人绑架了枫香，所以今天的歌赫娜由朱莉提供。但是由于某些众所周知的原因，今天的午饭不仅无法正常开饭，为师的大可爱还需要处理这些活蹦乱跳冒着绿色粘液的午饭，将枫香救出来!## 题目描述为师的日奈大可爱需要在的 $n \times m$ 的歌赫娜餐厅中围剿这些活蹦乱跳的午饭，**她现在在餐厅的 $(x_1,y_1)$ 处**，但由于其重量太大且移动速度极其缓慢，因此将其看作不动的点，则 $a_{i,j} > 0$，其余点则没有这些午餐，则 $a_{i,j} = 0$。为师的日奈大可爱聪明精干，**跑一格只需要一个单位时间，收拾一份午饭只需要 $a_{i,j}$ 单位个时间**。难缠的午饭会在日奈收拾过离开后便会恢复。现在美食研究会的晴奈等人将枫香放置在某个没有午餐的点 $(hx,hy)$ 上，由泉把守，使得**枫香无法移动**。已知，**日奈在到达枫香的位置后便能将她救下(无需消耗额外时间，即日奈到达枫香所在格后枫香下一时刻便可以自行走路)**，但是日奈会选择追击美食研究会等人，所以之后的路需要枫香自己走。**枫香跑一格需要一个单位时间**，且无力清理午饭，她需要自行跑到 $(x_2,y_2)$ 处坐上伊吕波的虎丸号撤离。设日奈出发的时刻为 $0$。本题求枫香最快在哪一个时刻 $t$ 能够坐上虎丸号撤离。## 输入格式共 $n + 4$ 行。第一行，两个正整数 $n,m$。第二行，两个正整数 $x_1,y_1$。第三行，两个正整数 $x_2,y_2$。第四行，两个正整数 $hx,hy$。接下来 $n$ 行，每行 $m$ 个正整数，每个数是 $a_{i,j}$。## 输出格式共一行。输出一个正整数 $t$。## 输入输出样例 #1### 输入 #15 5
1 2
5 4
1 4
0 0 10 0 10
10 0 1 0 10
10 0 10 0 0
10 0 10 10 0
10 0 0 0 0
### 输出 #111
## 说明/提示对于 $100\%$ 的数据。$n,m \le 1 \times 10 ^3$。$1 \le x_1,x_2,hx \le n$。$1 \le y_1,y_2,hy \le m$。$0 \le a_{i,j} \le 1 \times 10 ^ 9$。