分数: 450 点
问题陈述
有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 每个单元格上放置一些硬币,并且有 A_{i,j} 手机上有硬币 (i,j).
高桥最初在牢房 (1,1) 并且有 x 硬币。 在接下来的 H+W-1 天,几件事情将会发生。 上 k第一天 (1\leq k\leq H+W-1),以下事情按顺序发生:
- 高桥收集了他当前所在牢房中放置的所有硬币。
- 饥饿的高桥消耗 P_k 他手里有硬币可以买食物。但是,如果他的数量少于 P_k 硬币,他无法购买食物并因饥饿而崩溃。
- If k < H+W-1,Takahashi 向右移动一个单元格或向下移动一个单元格。他不能离开网格。如果 k=H+W-1,他什么也没做。
当高桥有办法完成下一个时 H+W-1 没有因饥饿而崩溃的天数,求最小非负整数 x 是高桥最初拥有的硬币数量。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}
输出
输出答案。
示例输入 1
2 2 3 2 4 1 1 3 6
示例输出 1
2
当 x=2,高桥可以采取以下行动来避免饿倒:
- 最初,他在牢房 (1,1) 并且有 2 硬币。
- 天 1:
- 他收集 3 硬币放在单元格上 (1,1),所以他有 5 硬币。
- 他消耗 1 硬币买食物,所以他有 4 硬币。
- 他移至牢房 (2,1) 这是 1 如下。
- 天 2:
- 他收集 4 硬币放在单元格上 (2,1),所以他有 8 硬币。
- 他消耗 3 硬币可以买食物,所以他有 5 硬币。
- 他移至牢房 (2,2) 这是 1 在右边。
- 天 3:
- 他收集 1 硬币放在电池上 (2,2),所以他有 6 硬币。
- 他消耗 6 硬币可以买食物,所以他有 0 硬币。
当 x is 1 或更少,无论高桥如何行动,他都会在某个时候因饥饿而崩溃。 因此,答案是 2.
示例输入 2
1 1 5 3
示例输出 2
0
即使高桥一开始没有金币,他也不会饿倒。
示例输入 3
4 7 35 29 36 88 58 15 25 99 7 49 61 67 4 57 96 92 3 49 49 36 90 72 89 40 44 24 53 45 55 43 23 71 77 6 94 19 27 21
示例输出 3
20