[Cnoi2020]雷雨

题目背景

> 令人不安的云开始笼罩天空。 巨大的建筑在强风中轧轧作响。 幻想乡中响彻着不和协音。 ——「东方辉针城 ~ Double Dealing Character」 一个雷雨交加的夜晚,一束闪电击中了雾之湖畔的红魔馆和迷途竹林。 似乎有什么大事要发生,Cirno 在小屋静静地中思考着。

题目描述

幻想乡的纵切面可以抽象成一个 $n\times m$ 的矩形。 其中每一个 $1\times 1$ 的单元格 $(i,j)$ 都有一个**电阻计量值**(虚构的概念) $R_{i,j}$。 闪电从**雷雨云**上的 $\texttt{O}(n,a)$ 发出,击中了**地面**上的*红魔馆* $\texttt{A}(1,b)$ 与*迷途竹林* $\texttt{B}(1,c)$。 雷电是自然的造物,所以覆盖的位置电阻计量值总和最小,即从 $\texttt{O}$ 到 $\texttt{A}$ 与 $\texttt{B}$ 的**两条路径的并集**的电阻计量值的和最小。 所以在所有位置电阻计量已知的情况下,Cirno 想知道雷电的经过的路径的最小电阻计量值的和。

输入输出格式

输入格式


第一行,五个整数 $n,m,a,b,c$。$(0<a,b,c\le m)$ 以下 $n$ 行,每行 $m$ 个整数,表示电阻计量 $R_{i,j}$,其中第一行表示雷雨云,最后一行表示地面。

输出格式


一行,一个整数,表示答案。

输入输出样例

输入样例 #1

5 5 1 2 4
1 8 1 6 6
1 1 1 2 4
8 3 1 2 2
1 2 1 9 1
1 0 9 1 1

输出样例 #1

15

说明

## 样例解释 ![](https://cdn.opensource-notebook.com/upload/image_hosting/7ozs40i3.png) 如图黄色线为闪电的路径。 ## 数据范围与约定 对于 $100\%$ 的数据保证:$0<n,m \le 1000$,$0 \le R_{i,j}\le 10^9$,$0< a,b,c \le m$。 #### 子任务「本题采用捆绑测试」 - Subtask1($10\%$): $R_{i,j}\in\{1\}$。 - Subtask2($10\%$): $R_{i,j}\in\{0,1\}$。 - Subtask3($10\%$): $a=b=c$。 - Subtask4($10\%$): $n,m \le 5$。 - Subtask5($60\%$): 无特殊限制。