Score: $550$ points

问题陈述

存在一个 $N$ 行和 $N$ 列的网格。令 $(i,j)$ 表示从上到下的第 $i$ 行和从左到右的第 $j$ 列的方格。

高桥最初在方格 $(1,1)$ 处，此时他的钱为零。

当高桥处于方格 $(i,j)$ 时，他可以在一个 行动 中执行以下操作之一：

• 保持在原地，并将他的钱增加 $P_{i,j}$。
• 从他的钱中支付 $R_{i,j}$，然后移动到方格 $(i,j+1)$。
• 从他的钱中支付 $D_{i,j}$，然后移动到方格 $(i+1,j)$。

他不能做出使他的钱变为负数或使他超出网格范围的移动。

如果高桥采取最优策略，他需要多少个行动才能到达方格 $(N,N)$？

以上为通义千问 qwen-max 翻译，仅供参考。

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