Minimum Cost to Move Within a Grid (Akuna Shang Hai )

In a rectangular grid you can only move up, down, left or right. Crossing between rows i and i+1 in any column costs costRows[i]; crossing between columns j and j+1 in any row costs costCols[j]. Find the minimum total cost from the start to the destination. The statement gives no obstacle positions, so this site interprets the whole grid as passable.

输入格式

The first line contains rows cols initR initC finalR finalC, with 0-based coordinates; the second line contains rows−1 costs between rows; the third line contains cols−1 costs between columns. Original: 1≤rows,cols≤100000, coordinates are valid, and 0≤(cost of each edge)≤10000.

输出格式

Output the minimum movement cost.

样例 1

输入：

3 3 0 0 1 2
5 2
6 1

输出：

12

样例 2

输入：

4 4 1 2 3 3
1 2 3
7 8 9

输出：

14

样例 3

输入：

1 1 0 0 0 0

输出：

0