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 $ ならば、高橋君が、そのときいるマスの $ 1 $ つ右または $ 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} $

答えを出力せよ。

### Sample Explanation 1 $ x=2 $ のとき、高橋君は次のように行動することで、一度も空腹で倒れずに済みます。 - 最初、マス $ (1,1) $ におり、 $ 2 $ 枚のコインを所持している。 - $ 1 $ 日目： 1. マス $ (1,1) $ に置かれたコイン $ 3 $ 枚を回収し、手持ちのコインが $ 5 $ 枚になる。 2. コインを $ 1 $ 枚消費してご飯を買い、手持ちのコインが $ 4 $ 枚になる。 3. $ 1 $ つ下にあるマス $ (2,1) $ に移動する。 - $ 2 $ 日目： 1. マス $ (2,1) $ に置かれたコイン $ 4 $ 枚を回収し、手持ちのコインが $ 8 $ 枚になる。 2. コインを $ 3 $ 枚消費してご飯を買い、手持ちのコインが $ 5 $ 枚になる。 3. $ 1 $ つ右にあるマス $ (2,2) $ に移動する。 - $ 3 $ 日目： 1. マス $ (2,2) $ に置かれたコイン $ 1 $ 枚を回収し、手持ちのコインが $ 6 $ 枚になる。 2. コインを $ 6 $ 枚消費してご飯を買い、手持ちのコインが $ 0 $ 枚になる。 $ x $ が $ 1 $ 以下のとき、高橋君はどのように行動してもいずれかのタイミングで空腹で倒れてしまいます。 よって答えは $ 2 $ です。 ### Sample Explanation 2 最初に $ 1 $ 枚もコインを持っていなかったとしても、高橋君は空腹で倒れることはありません。 ### 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 $ - 入力は全て整数