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}$

输出答案。

## 限制条件 - $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 翻译