Background

Uneasy clouds begin to cover the sky.
Huge buildings creak in the strong wind.
Discordant sounds echo throughout Gensokyo.
— “Touhou Kishinjou ~ Double Dealing Character”.

On a stormy night with thunder and lightning, a bolt of lightning struck the Scarlet Devil Mansion by the Misty Lake and the Bamboo Forest of the Lost.

It seems that something big is about to happen, and Cirno is quietly thinking in her hut.

Problem Description

The vertical cross-section of Gensokyo can be abstracted as an $n \times m$ rectangle.

Each $1 \times 1$ cell $(i,j)$ has a resistance measurement value (a fictional concept) $R_{i,j}$.

The lightning is emitted from $\texttt{O}(n,a)$ on the thundercloud, and hits the Scarlet Devil Mansion $\texttt{A}(1,b)$ and the Bamboo Forest of the Lost $\texttt{B}(1,c)$ on the ground.

Since lightning is a natural creation, it will choose positions so that the total resistance measurement value is minimized. That is, the sum of resistance measurement values over the union of the two paths from $\texttt{O}$ to $\texttt{A}$ and $\texttt{B}$ is minimized.

So, when the resistance measurements at all positions are known, Cirno wants to know the minimum possible sum of resistance measurement values along the lightning’s paths.

Input Format

The first line contains five integers $n,m,a,b,c$. $(0<a,b,c\le m)$.

The next $n$ lines each contain $m$ integers, representing the resistance measurement $R_{i,j}$. The first row represents the thundercloud, and the last row represents the ground.

Output Format

One line with one integer, representing the answer.

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

Hint

Sample Explanation

As shown in the figure, the yellow lines are the lightning’s paths.

Constraints

For $100\%$ of the testdata, it is guaranteed that: $0<n,m \le 1000$, $0 \le R_{i,j}\le 10^9$, $0< a,b,c \le m$.

Subtasks “This problem uses bundled tests”

• Subtask 1 ($10\%$): $R_{i,j}\in\{1\}$.
• Subtask 2 ($10\%$): $R_{i,j}\in\{0,1\}$.
• Subtask 3 ($10\%$): $a=b=c$.
• Subtask 4 ($10\%$): $n,m \le 5$.
• Subtask 5 ($60\%$): No special constraints.

Translated by ChatGPT 5