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