luogu#P6833. [Cnoi2020] 雷雨

[Cnoi2020] 雷雨

题目背景

令人不安的云开始笼罩天空。
巨大的建筑在强风中轧轧作响。
幻想乡中响彻着不和协音。
——「东方辉针城 ~ Double Dealing Character」

一个雷雨交加的夜晚,一束闪电击中了雾之湖畔的红魔馆和迷途竹林。

似乎有什么大事要发生,Cirno 在小屋静静地中思考着。

题目描述

幻想乡的纵切面可以抽象成一个 n×mn\times m 的矩形。

其中每一个 1×11\times 1 的单元格 (i,j)(i,j) 都有一个电阻计量值(虚构的概念) Ri,jR_{i,j}

闪电从雷雨云上的 O(n,a)\texttt{O}(n,a) 发出,击中了地面上的红魔馆 A(1,b)\texttt{A}(1,b)迷途竹林 B(1,c)\texttt{B}(1,c)

雷电是自然的造物,所以覆盖的位置电阻计量值总和最小,即从 O\texttt{O}A\texttt{A}B\texttt{B}两条路径的并集的电阻计量值的和最小。

所以在所有位置电阻计量已知的情况下,Cirno 想知道雷电的经过的路径的最小电阻计量值的和。

输入格式

第一行,五个整数 n,m,a,b,cn,m,a,b,c(0<a,b,cm)(0<a,b,c\le m)

以下 nn 行,每行 mm 个整数,表示电阻计量 Ri,jR_{i,j},其中第一行表示雷雨云,最后一行表示地面。

输出格式

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

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
15

提示

样例解释

如图黄色线为闪电的路径。

数据范围与约定

对于 100%100\% 的数据保证:0<n,m10000<n,m \le 10000Ri,j1090 \le R_{i,j}\le 10^90<a,b,cm0< a,b,c \le m

子任务「本题采用捆绑测试」

  • Subtask1(10%10\%): Ri,j{1}R_{i,j}\in\{1\}
  • Subtask2(10%10\%): Ri,j{0,1}R_{i,j}\in\{0,1\}
  • Subtask3(10%10\%): a=b=ca=b=c
  • Subtask4(10%10\%): n,m5n,m \le 5
  • Subtask5(60%60\%): 无特殊限制。