AT_zone2021_e 潜入

有一个二维平面，你现在位于坐标 $(1, 1)$，想要移动到 UFO 所在的坐标 $(R, C)$。 当你在 $(r, c)$ 时，你可以进行以下 $4$ 种移动： - 从 $(r, c)$ 移动到 $(r, c + 1)$，花费 $A_{r, c}$ 的代价。该移动仅当 $c < C$ 时可以使用。 - 从 $(r, c)$ 移动到 $(r, c - 1)$，花费 $A_{r, c - 1}$ 的代价。该移动仅当 $c > 1$ 时可以使用。 - 从 $(r, c)$ 移动到 $(r + 1, c)$，花费 $B_{r, c}$ 的代价。该移动仅当 $r < R$ 时可以使用。 - 选择一个满足 $1 \leq i < r$ 的整数 $i$，从 $(r, c)$ 移动到 $(r - i, c)$，花费 $1 + i$ 的代价。 请你求出从 $(1, 1)$ 移动到 $(R, C)$ 所需的最小代价。

输入按以下格式从标准输入读入。 > $R$ $C$ > $A_{1,1}$ $\cdots$ $A_{1,C-1}$ > $\vdots$ > $A_{R,1}$ $\cdots$ $A_{R,C-1}$ > $B_{1,1}$ $\cdots$ $B_{1,C}$ > $\vdots$ > $B_{R-1,1}$ $\cdots$ $B_{R-1,C}$

输出答案。

## 故事 在推进密码解读的过程中，你的伙伴 Moore 突然被 UFO 吸走了。Moore 几乎是独自一人开发了与 UFO 通信的系统，如果这样下去就无法与 UFO 通信了！ 你回想起黑心初创公司时代的死亡冲刺。巴士因子 $=1$ 的团队总是很脆弱。 没办法，只能亲自进入 UFO 内部与其对话了。你抬头望去，发现 UFO 放下了类似梯子的东西。 但仔细一看，梯子已经破烂不堪，部分地方已经腐烂脱落。你必须想办法巧妙地攀爬上去。 ## 约束条件 - 所有输入均为整数。 - $2 \leq R, C \leq 500$ - $0 \leq A_{i,j} < 10^3$ - $0 \leq B_{i,j} < 10^3$ ## 样例解释 1 如下移动可以达到总代价 $9$： - 从 $(1, 1)$ 移动到 $(2, 1)$，花费 $1$。 - 从 $(2, 1)$ 移动到 $(3, 1)$，花费 $1$。 - 从 $(3, 1)$ 移动到 $(3, 2)$，花费 $1$。 - 从 $(3, 2)$ 移动到 $(1, 2)$，花费 $3$。 - 从 $(1, 2)$ 移动到 $(1, 3)$，花费 $1$。 - 从 $(1, 3)$ 移动到 $(2, 3)$，花费 $1$。 - 从 $(2, 3)$ 移动到 $(3, 3)$，花费 $1$。 由 ChatGPT 4.1 翻译