/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
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) 日目には以下のことが順に起こります：
- 高橋君が、そのときいるマスに置かれたコインを全て回収する。
- お腹の空いた高橋君が、手持ちのコインを P_k 枚消費してご飯を買う。ただし、所持しているコインが P_k 枚未満の場合ご飯を買うことはできず、空腹のあまり倒れてしまう。
- k < H+W-1 ならば、高橋君が、そのときいるマスの 1 つ右または 1 つ下のいずれかのマスを選んでそこに移動する。ただし、グリッドの外に出てしまうような移動はできない。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,1) に置かれたコイン 3 枚を回収し、手持ちのコインが 5 枚になる。
- コインを 1 枚消費してご飯を買い、手持ちのコインが 4 枚になる。
- 1 つ下にあるマス (2,1) に移動する。
- 2 日目：
- マス (2,1) に置かれたコイン 4 枚を回収し、手持ちのコインが 8 枚になる。
- コインを 3 枚消費してご飯を買い、手持ちのコインが 5 枚になる。
- 1 つ右にあるマス (2,2) に移動する。
- 3 日目：
- マス (2,2) に置かれたコイン 1 枚を回収し、手持ちのコインが 6 枚になる。
- コインを 6 枚消費してご飯を買い、手持ちのコインが 0 枚になる。
x が 1 以下のとき、高橋君はどのように行動してもいずれかのタイミングで空腹で倒れてしまいます。 よって答えは 2 です。
入力例 2
1 1 5 3
出力例 2
0
最初に 1 枚もコインを持っていなかったとしても、高橋君は空腹で倒れることはありません。
入力例 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
Score : 450 points
Problem Statement
There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Some coins are placed on each cell, and there are A_{i,j} coins on cell (i,j).
Takahashi is initially at cell (1,1) and has x coins. Over the next H+W-1 days, several events will occur. On the k-th day (1\leq k\leq H+W-1), the following things happen in order:
- Takahashi collects all the coins placed on the cell where he is currently located.
- Hungry Takahashi consumes P_k coins from his hand to buy food. However, if he has fewer than P_k coins, he cannot buy food and collapses from hunger.
- If k < H+W-1, Takahashi moves either one cell right or one cell down. He cannot leave the grid. If k=H+W-1, he does nothing.
When there exists a way for Takahashi to finish the next H+W-1 days without ever collapsing from hunger, find the minimum non-negative integer x that can be the number of coins Takahashi initially has.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Output the answer.
Sample Input 1
2 2 3 2 4 1 1 3 6
Sample Output 1
2
When x=2, Takahashi can act as follows to avoid collapsing from hunger:
- Initially, he is at cell (1,1) and has 2 coins.
- Day 1:
- He collects 3 coins placed on cell (1,1), so he has 5 coins.
- He consumes 1 coin to buy food, so he has 4 coins.
- He moves to cell (2,1) which is 1 below.
- Day 2:
- He collects 4 coins placed on cell (2,1), so he has 8 coins.
- He consumes 3 coins to buy food, so he has 5 coins.
- He moves to cell (2,2) which is 1 to the right.
- Day 3:
- He collects 1 coin placed on cell (2,2), so he has 6 coins.
- He consumes 6 coins to buy food, so he has 0 coins.
When x is 1 or less, Takahashi will collapse from hunger at some point no matter how he acts. Therefore, the answer is 2.
Sample Input 2
1 1 5 3
Sample Output 2
0
Even if Takahashi initially has no coins, he will not collapse from hunger.
Sample Input 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
Sample Output 3
20