← 返回题目列表

AtCoder · abc415_e

H. 饥饿的高桥

中文机器翻译题面 查看原题

分数: 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),以下事情按顺序发生:

  1. 高桥收集了他当前所在牢房中放置的所有硬币。
  2. 饥饿的高桥消耗 P_k 他手里有硬币可以买食物。但是,如果他的数量少于 P_k 硬币,他无法购买食物并因饥饿而崩溃。
  3. 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:
    1. 他收集 3 硬币放在单元格上 (1,1),所以他有 5 硬币。
    2. 他消耗 1 硬币买食物,所以他有 4 硬币。
    3. 他移至牢房 (2,1) 这是 1 如下。
  • 天 2:
    1. 他收集 4 硬币放在单元格上 (2,1),所以他有 8 硬币。
    2. 他消耗 3 硬币可以买食物,所以他有 5 硬币。
    3. 他移至牢房 (2,2) 这是 1 在右边。
  • 天 3:
    1. 他收集 1 硬币放在电池上 (2,2),所以他有 6 硬币。
    2. 他消耗 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