/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
縦 N 行横 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。
高橋君は最初マス (1,1) におり、所持金は 0 です。
高橋君はマス (i,j) にいるとき、1 回の行動で以下のいずれかを行うことができます。
- 同じマスにとどまり、所持金を P_{i,j} 増やす。
- 所持金から R_{i,j} 払ってマス (i,j+1) に移動する。
- 所持金から D_{i,j} 払ってマス (i+1,j) に移動する。
所持金が負になる移動、グリッドの外に出る移動はできません。
高橋君が最適に行動したとき、何回の行動でマス (N,N) にたどり着くことができますか。
制約
- 2 \leq N \leq 80
- 1 \leq P_{i,j} \leq 10^9
- 1 \leq R_{i,j},D_{i,j} \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N
P_{1,1} \ldots P_{1,N}
\vdots
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}
出力
答えを出力せよ。
入力例 1
3 1 2 3 3 1 2 2 1 1 1 2 4 3 4 2 1 5 7 5 3 3
出力例 1
8
以下のようにして 8 回の行動でマス (3,3) にたどり着くことができます。
- マス (1,1) にとどまり、所持金を 1 増やす。所持金は 1 になる。
- 所持金から 1 払ってマス (2,1) に移動する。所持金は 0 になる。
- マス (2,1) にとどまり、所持金を 3 増やす。所持金は 3 になる。
- マス (2,1) にとどまり、所持金を 3 増やす。所持金は 6 になる。
- マス (2,1) にとどまり、所持金を 3 増やす。所持金は 9 になる。
- 所持金から 4 払ってマス (2,2) に移動する。所持金は 5 になる。
- 所持金から 3 払ってマス (3,2) に移動する。所持金は 2 になる。
- 所持金から 2 払ってマス (3,3) に移動する。所持金は 0 になる。
入力例 2
3 1 1 1 1 1 1 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 2
4000000004
Score: 550 points
Problem Statement
There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
Takahashi is initially at square (1,1) with zero money.
When Takahashi is at square (i,j), he can perform one of the following in one action:
- Stay at the same square and increase his money by P_{i,j}.
- Pay R_{i,j} from his money and move to square (i,j+1).
- Pay D_{i,j} from his money and move to square (i+1,j).
He cannot make a move that would make his money negative or take him outside the grid.
If Takahashi acts optimally, how many actions does he need to reach square (N,N)?
Constraints
- 2 \leq N \leq 80
- 1 \leq P_{i,j} \leq 10^9
- 1 \leq R_{i,j},D_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
P_{1,1} \ldots P_{1,N}
\vdots
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}
Output
Print the answer.
Sample Input 1
3 1 2 3 3 1 2 2 1 1 1 2 4 3 4 2 1 5 7 5 3 3
Sample Output 1
8
It is possible to reach square (3,3) in eight actions as follows:
- Stay at square (1,1) and increase money by 1. His money is now 1.
- Pay 1 money and move to square (2,1). His money is now 0.
- Stay at square (2,1) and increase money by 3. His money is now 3.
- Stay at square (2,1) and increase money by 3. His money is now 6.
- Stay at square (2,1) and increase money by 3. His money is now 9.
- Pay 4 money and move to square (2,2). His money is now 5.
- Pay 3 money and move to square (3,2). His money is now 2.
- Pay 2 money and move to square (3,3). His money is now 0.
Sample Input 2
3 1 1 1 1 1 1 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 2
4000000004