AT_abc344_f [ABC344F] Earn to Advance

题目描述

有一个纵向 $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}$
$\vdots$
$P_{N,1}$ $...$ $P_{N,N}$
$R_{1,1}$ $...$ $R_{1,N-1}$
$\vdots$
$R_{N,1}$ $...$ $R_{N,N-1}$
$D_{1,1}$ $...$ $D_{1,N}$
$\vdots$
$D_{N-1,1}$ $...$ $D_{N-1,N}$

输出格式

输出答案。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

限制条件

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

样例解释 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$。

由 ChatGPT 4.1 翻译