AT_abc415_e [ABC415E] Hungry Takahashi

有一个 $H$ 行 $W$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。每个格子上都放有若干枚硬币，格子 $(i,j)$ 上放有 $A_{i,j}$ 枚硬币。 高桥君一开始站在格子 $(1,1)$，手上持有 $x$ 枚硬币。接下来将会有 $H+W-1$ 天发生一些事件。第 $k$ 天（$1\leq k\leq H+W-1$）会依次发生以下事情： 1. 高桥君会把当前所在格子上的所有硬币全部捡起来。 2. 饥饿的高桥君会用手上的 $P_k$ 枚硬币买饭。如果他手上的硬币不足 $P_k$ 枚，则无法买饭，会因为饥饿而倒下。 3. 如果 $k < H+W-1$，高桥君会选择向右或向下移动一格，进入相邻的格子。不能移动到网格外。如果 $k=H+W-1$，则不再移动。 请你求出，使得高桥君能够在 $H+W-1$ 天内从未因饥饿倒下的情况下，初始持有硬币数 $x$ 的最小非负整数是多少。

输入按以下格式从标准输入给出。 > $H$ $W$ > $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$ > $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$ > $\vdots$ > $A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$ > $P_1$ $P_2$ $\dots$ $P_{H+W-1}$

请输出答案。

## 限制条件 - $H,W\geq 1$ - $H\times W \leq 2\times 10^5$ - $1\leq A_{i,j}\leq 10^9$ - $1\leq P_k\leq 10^9$ - 所有输入均为整数 ## 样例解释 1 当 $x=2$ 时，高桥君可以按如下方式行动，保证从未因饥饿倒下。 - 一开始在格子 $(1,1)$，手上有 $2$ 枚硬币。 - 第 $1$ 天： 1. 捡起格子 $(1,1)$ 上的 $3$ 枚硬币，手上有 $5$ 枚。 2. 用 $1$ 枚硬币买饭，剩下 $4$ 枚。 3. 向下移动到 $(2,1)$。 - 第 $2$ 天： 1. 捡起格子 $(2,1)$ 上的 $4$ 枚硬币，手上有 $8$ 枚。 2. 用 $3$ 枚硬币买饭，剩下 $5$ 枚。 3. 向右移动到 $(2,2)$。 - 第 $3$ 天： 1. 捡起格子 $(2,2)$ 上的 $1$ 枚硬币，手上有 $6$ 枚。 2. 用 $6$ 枚硬币买饭，剩下 $0$ 枚。 当 $x\leq 1$ 时，无论如何行动，高桥君都会在某个时刻因饥饿倒下。因此答案为 $2$。 ## 样例解释 2 即使一开始没有持有任何硬币，高桥君也不会因饥饿倒下。 由 ChatGPT 4.1 翻译