/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
ストーリー
暗号解読を進めていると、仲間のムーアが突如 UFO に吸い込まれ、連れ去られてしまった。
ムーアは UFO との通信システムをほぼ 1 人で開発していたため、このままでは UFO と交信することができない！
デスマーチが横行していたブラックスタートアップ時代を思い出す。
バス係数{} = 1 のチームはいつだって脆いものだ。
仕方がない、UFO 内に乗り込んで直接話すしかなさそうだ。
上空を見上げると、UFO から梯子のようなものが下されている。
だがよく見るとボロボロで所々腐り落ちているようだ。
どうにかしてうまい登り方を考えなければ。
問題文
2 次元平面があり、あなたは今いる座標 (1, 1) から UFO のある座標 (R, C) に移動したいです。
あなたが (r, c) にいるとき、あなたは以下の 4 種類の移動を行うことができます。
- (r, c) から (r, c + 1) に移動する。A_{r, c} のコストがかかる。この移動は c < C のとき使える。
- (r, c) から (r, c - 1) に移動する。A_{r, c - 1} のコストがかかる。この移動は c > 1 のとき使える。
- (r, c) から (r + 1, c) に移動する。B_{r, c} のコストがかかる。この移動は r < R のとき使える。
- 1 ≤ i < r を満たす整数 i を 1 つ選び、(r, c) から (r - i, c) に移動する。1 + i のコストがかかる。
(1, 1) から (R, C) に移動するために必要な最小のコストを求めてください。
制約
- 入力は全て整数
- 2 ≤ R, C ≤ 500
- 0 ≤ A_{i,j} < 10^3
- 0 ≤ B_{i,j} < 10^3
入力
入力は以下の形式で標準入力から与えられる。
R C
A_{1,1} \cdots A_{1,C-1}
\vdots
A_{R,1} \cdots A_{R,C-1}
B_{1,1} \cdots B_{1,C}
\vdots
B_{R-1,1} \cdots B_{R-1,C}
出力
答えを出力せよ。
入力例 1
3 3 10 1 10 10 1 10 1 10 1 1 10 1
出力例 1
9
以下のように移動するとコスト 9 が達成できます。
- (1, 1) から (2, 1) に移動する。コストが 1 かかる。
- (2, 1) から (3, 1) に移動する。コストが 1 かかる。
- (3, 1) から (3, 2) に移動する。コストが 1 かかる。
- (3, 2) から (1, 2) に移動する。コストが 3 かかる。
- (1, 2) から (1, 3) に移動する。コストが 1 かかる。
- (1, 3) から (2, 3) に移動する。コストが 1 かかる。
- (2, 3) から (3, 3) に移動する。コストが 1 かかる。
入力例 2
7 11 42 77 94 76 40 66 43 28 66 23 27 34 41 31 83 13 64 69 81 82 23 81 0 22 39 51 4 37 84 43 62 37 82 86 26 67 45 78 85 2 79 18 72 62 68 84 69 88 19 48 0 27 21 51 71 13 87 45 39 11 74 57 32 0 97 41 87 96 17 98 69 58 76 32 51 16 38 68 86 82 64 53 47 33 7 51 75 43 14 96 86 70 80 58 12 76 94 50 59 2 1 54 25 14 14 62 28 12 43 15 70 65 44 41 56 50 50 54 53 34 16 3 2 59 88 27 85 50 79 48 86 27 81 78 78 64
出力例 2
498
入力例 3
4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 3
0
Score : 500 points
Problem Statement
On a two-dimensional plane, you are now at coordinate (1, 1) and want to get to (R, C), the coordinates of the UFO.
When you are at (r, c), you can make the following four kinds of moves:
- Move from (r, c) to (r, c + 1) at the cost of A_{r, c}. You can make this move when c < C.
- Move from (r, c) to (r, c - 1) at the cost of A_{r, c - 1}. You can make this move when c > 1.
- Move from (r, c) to (r + 1, c) at the cost of B_{r, c}. You can make this move when r < R.
- Choose an integer i such that 1 ≤ i < r and move from (r, c) to (r - i, c) at the cost of 1 + i.
Find the minimum cost needed to move from (1, 1) to (R, C).
Constraints
- All values in input are integers.
- 2 ≤ R, C ≤ 500
- 0 ≤ A_{i,j} < 10^3
- 0 ≤ B_{i,j} < 10^3
Input
Input is given from Standard Input in the following format:
R C
A_{1,1} \cdots A_{1,C-1}
\vdots
A_{R,1} \cdots A_{R,C-1}
B_{1,1} \cdots B_{1,C}
\vdots
B_{R-1,1} \cdots B_{R-1,C}
Output
Print the answer.
Sample Input 1
3 3 10 1 10 10 1 10 1 10 1 1 10 1
Sample Output 1
9
You can achieve the cost of 9 as follows:
- Move from (1, 1) to (2, 1) at the cost of 1.
- Move from (2, 1) to (3, 1) at the cost of 1.
- Move from (3, 1) to (3, 2) at the cost of 1.
- Move from (3, 2) to (1, 2) at the cost of 3.
- Move from (1, 2) to (1, 3) at the cost of 1.
- Move from (1, 3) to (2, 3) at the cost of 1.
- Move from (2, 3) to (3, 3) at the cost of 1.
Sample Input 2
7 11 42 77 94 76 40 66 43 28 66 23 27 34 41 31 83 13 64 69 81 82 23 81 0 22 39 51 4 37 84 43 62 37 82 86 26 67 45 78 85 2 79 18 72 62 68 84 69 88 19 48 0 27 21 51 71 13 87 45 39 11 74 57 32 0 97 41 87 96 17 98 69 58 76 32 51 16 38 68 86 82 64 53 47 33 7 51 75 43 14 96 86 70 80 58 12 76 94 50 59 2 1 54 25 14 14 62 28 12 43 15 70 65 44 41 56 50 50 54 53 34 16 3 2 59 88 27 85 50 79 48 86 27 81 78 78 64
Sample Output 2
498
Sample Input 3
4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 3
0