I. Intersections
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the city, there are $$$n$$$ rows and $$$m$$$ columns totaling $$$n \cdot m$$$ intersections, and the intersection of row $$$i$$$, column $$$j$$$ has two properties $$$a_{i,j}$$$, $$$b_{i,j}$$$. We may use a pair of integers $$$(i, j)$$$ to denote the intersection of row $$$i$$$ and column $$$j$$$.

When the pedestrian is at intersection $$$(i, j)$$$, for any non-negative integer $$$k$$$:

  • If the current time is in $$$[k\cdot a_{i,j}+k\cdot b_{i,j}, (k+1)\cdot a_{i,j}+k\cdot b_{i,j})$$$, the pedestrian can choose to walk to intersection $$$(i - 1, j)$$$ if $$$i \gt 1$$$, or intersection $$$(i+1, j)$$$ if $$$i \lt n$$$.
  • If the current time is in $$$[(k+1)\cdot a_{i,j}+k\cdot b_{i,j}, (k+1)\cdot a_{i,j}+(k+1)\cdot b_{i,j})$$$, the pedestrian can choose to walk to intersection $$$(i, j-1)$$$ if $$$j \gt 1$$$, or intersection $$$(i, j+1)$$$ if $$$j \lt m$$$.

You can choose to remain stationary in place. It takes $$$c_{i,j}$$$ time to walk between $$$(i, j)$$$ and $$$(i, j+1)$$$ in either direction, and $$$w_{i,j}$$$ time to walk between $$$(i, j)$$$ and $$$(i+1, j)$$$ in either direction. It takes no time to pass through the intersection.

At the moment $$$0$$$, you are at intersection $$$(x_s, y_s)$$$ and you want to go to intersection $$$(x_t, y_t)$$$. What is the minimum amount of time it will take?

Input

The first line of six positive integers $$$n,m,x_s,y_s,x_t,y_t\ (2\le n,m\le 500,1\le x_s,x_t\le n, 1\le y_s,y_t\le m)$$$, with the meanings described in the problem statement.

For the next $$$n$$$ lines, each contains $$$m$$$ positive integers. The $$$j$$$-th number in line $$$i$$$ represents the property $$$a_{i,j}\ (1\le a_{i,j}\le 10^9)$$$ of intersection $$$(i, j)$$$.

For the next $$$n$$$ lines, each contains $$$m$$$ positive integers. The $$$j$$$-th number in line $$$i$$$ represents the property $$$b_{i,j}\ (1\le b_{i,j}\le 10^9)$$$ of intersection $$$(i, j)$$$.

For the next $$$n$$$ lines, each contains $$$m-1$$$ positive integers. The $$$j$$$-th number in line $$$i$$$ represents the road length $$$c_{i,j}\ (1\le c_{i,j}\le 10^9)$$$ between intersection $$$(i, j)$$$ and intersection $$$(i, j+1)$$$.

For the next $$$n-1$$$ lines, each contains $$$m$$$ positive integers. The $$$j$$$-th number in line $$$i$$$ represents the road length $$$w_{i,j}\ (1\le w_{i,j}\le 10^9)$$$ between intersection $$$(i, j)$$$ and intersection $$$(i+1, j)$$$.

Output

Output one integer in a line, representing the answer.

Example
Input
5 5 1 1 5 1
5 3 3 3 3
1 5 4 5 5
2 1 4 3 4
5 2 4 1 2
2 4 5 2 3
2 2 5 1 5
4 1 4 5 3
3 5 5 1 5
3 3 2 2 4
3 2 2 2 5
8 2 9 7
1 5 4 7
2 6 10 8
3 10 2 10
8 7 9 9
9 6 2 1 1
2 8 4 6 4
10 4 1 6 5
8 8 4 10 4
Output
33