赚钱前进

题目描述

有一个 $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)$ 需要多少次行动？

输入格式

输入按以下格式从标准输入给出：

N
P_{1,1} … P_{1,N}
⋮
P_{N,1} … P_{N,N}
R_{1,1} … R_{1,N-1}
⋮
R_{N,1} … R_{N,N-1}
D_{1,1} … D_{1,N}
⋮
D_{N-1,1} … D_{N-1,N}

输出格式

输出答案。

样例

3
1 2 3
3 1 2
2 1 1
1 2
4 3
4 2
1 5 7
5 3 3

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。

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

4000000004

数据范围

• $2 \le N \le 80$
• $1 \le P_{i,j} \le 10^9$
• $1 \le R_{i,j},D_{i,j} \le 10^9$
• 输入均为整数