#653. [Cnoi2020] 雷雨

[Cnoi2020] 雷雨

题目描述

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

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

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

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

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

输入格式

第一行,五个整数 n,m,a,b,cn,m,a,b,c。$(0

输出格式

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

样例

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

题目来源:洛谷 P6833