103445: [Atcoder]ABC344 F - Earn to Advance

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

问题描述

有一个$N$行$N$列的网格。让$(i,j)$表示从顶部第$i$行、从左部第$j$列的格子。

一开始，高桥凉平在格子$(1,1)$，拥有0元钱。

当高桥凉平在格子$(i,j)$时，他可以在一个动作中进行以下一项：

• 留在原地，增加他的钱$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