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 翻译