分数: 550 点
问题陈述
有一个网格 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)?
约束
- 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

可以到达广场 (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