AT_abc415_e [ABC415E] Hungry Takahashi

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: 1. Takahashi collects all the coins placed on the cell where he is currently located. 2. 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. 3. 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.

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 the answer.

### Sample Explanation 1 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 $ : 1. He collects $ 3 $ coins placed on cell $ (1,1) $ , so he has $ 5 $ coins. 2. He consumes $ 1 $ coin to buy food, so he has $ 4 $ coins. 3. He moves to cell $ (2,1) $ which is $ 1 $ below. - Day $ 2 $ : 1. He collects $ 4 $ coins placed on cell $ (2,1) $ , so he has $ 8 $ coins. 2. He consumes $ 3 $ coins to buy food, so he has $ 5 $ coins. 3. He moves to cell $ (2,2) $ which is $ 1 $ to the right. - Day $ 3 $ : 1. He collects $ 1 $ coin placed on cell $ (2,2) $ , so he has $ 6 $ coins. 2. 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 Explanation 2 Even if Takahashi initially has no coins, he will not collapse from hunger. ### 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.