U517213 魔幻地图

[2024 年婺城区信息素养大赛](https://www.luogu.com.cn/training/675768) T4

老师在求学期间，除了修炼魔法课，还开发了一种能创造虚拟的魔幻地图的技能。在不同的地图中，大家可以进行不同的闯关游戏，深受大家的喜爱。这天，经历了一整天疲惫的学习之后，魔幻之旅又开始了。 首先，老师将将游玩者移送至图中的出发点。地图可以看成是一个的网格。从上到下，从左到右，编号都为 $1 \dots N$。其中： - 位于最左上角的网格 $(1,1)$，就是游玩者的出发点。 - 位于最右下角的网格 $(N,N)$，就是游玩者的结束点。 在魔幻地图中，游玩者会被赋予魔法能力，但是使用魔法需要消耗元气值。初始时，游玩者的元气值为 $0$。游玩者的目标是尽早地到达结束点。 游玩者在位置 $(i,j)$ 时，**每一秒**，他都有三种选择： - 停留在原地，则恢复元气值 $a_{i,j}$； - 使用魔法，消耗 $b_{i,j}$ 元气值，则可以移动到 $(i,j+1)$； - 使用魔法，消耗 $c_{i,j}$ 元气值，则可以移动到 $(i+1,j)$； 老师还规定，任何时刻，在魔幻地图内游玩者的元气值**不能低于 $0$**。老师需要大家来帮忙计算出从出发点到结束点所需的最少时间，第一个计算出的同学可以优先进入魔幻地图体验。

第一行，一个整数 $N$。接下来 $N$ 行 $N$ 列的数组，其中 $a_{i,j}$ 表示在地图的 $(i,j)$ 处每秒钟能恢复的元气值： $$ \begin{matrix} a_{1,1} & a_{1,2} & \dots & a_{1,N} \\ a_{2,1} & a_{2,2} & \dots & a_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N,1} & a_{N,2} & \dots & a_{N,N} \end{matrix} $$ 接下来 $N$ 行 $N-1$ 列的数组，其中 $b_{i,j}$ 表示从 $(i,j)$ 移动到 $(i,j+1)$ 需要消耗的元气值： $$ \begin{matrix} b_{1,1} & b_{1,2} & \dots & b_{1,N-1} \\ b_{2,1} & b_{2,2} & \dots & b_{2,N-1} \\ \vdots & \vdots & \ddots & \vdots \\ b_{N,1} & b_{N,2} & \dots & b_{N,N-1} \end{matrix} $$ 接下来 $N-1$ 行 $N$ 列的数组，其中 $c_{i,j}$ 表示从 $(i,j)$ 移动到 $(i+1,j)$ 需要消耗的元气值： $$ \begin{matrix} c_{1,1} & c_{1,2} & \dots & c_{1,N} \\ c_{2,1} & c_{2,2} & \dots & c_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ c_{N-1,1} & c_{N-1,2} & \dots & c_{N-1,N} \end{matrix} $$

计算游玩者到达结束点所需的最少时间。

【样例解释】 - 停留在 $(1,1)$ 处 $1$ 秒，当前元气值为 $1$； - 消耗 $1$ 点元气值，移至 $(2,1)$, 当前总用时 $2$ 秒，当前剩余元气值为 $0$； - 停留在 $(2,1)$ 处 $3$ 秒，当前总用时 $5$ 秒，当前元气值为 $9$； - 消耗 $4$ 点元气值，移至 $(2,2)$，当前总用时 $6$ 秒，当前剩余元气值为 $5$； - 消耗 $3$ 点元气值，移至 $(3,2)$，当前总用时 $7$ 秒，当前剩余元气值为 $2$； - 消耗 $2$ 点元气值，移至 $(3,3)$，当前总用时 $8$ 秒，当前剩余元气值为 $0$； 可能存在其他的移动方案，但是可以证明用时 $8$ 秒是最少需要的时间。 【数据范围】 对于 $10\%$ 的数据，数组 $a$，数组 $b$，数组 $c$ 的数值均相等。 对于 $100\%$ 的数据，数组 $a$，数组 $b$，数组 $c$ 的数值范围为：$[1,10^9]$ 对于 $100\%$ 的数据，$2 \le N \le 80$。