Problem Description

There is a section divided into $ H $ squares by $ W $ squares, totaling $H \times W$ squares. Except for the three squares at the bottom left corner, bottom right corner, and top right corner, all these squares are undeveloped, and the cost required to develop the square at the $ i $-th row from the top and the $ j $-th column from the left ( $1 \leq i \leq H, 1 \leq j \leq W$ ) is $ A_{i,j} $ yen.

An object is placed on the square at the bottom left corner of the section. You are trying to move this object first to the square at the bottom right corner, and then to the square at the top right corner.

The movement of the object is done by repeatedly moving it from the square it currently occupies to an adjacent square up, down, left, or right. At this time, all the squares the object passes through must be developed. Once a square has been developed, the object can pass over it any number of times.

Find the minimum total cost required to develop the squares.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ A_{1,1} $ $ A_{1,2} $ $\ldots$ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $\ldots$ $ A_{2,W} $ $ : $ $ A_{H,1} $ $ A_{H,2} $ $\ldots$ $ A_{H,W} $

Output Format

Output an integer representing the minimum total cost required.

Sample Input and Output

Sample Input #1

5 6
9 9 9 9 1 0
9 9 9 9 1 9
9 9 9 1 1 1
9 1 1 1 9 1
0 1 9 9 9 0

Sample Output #1

10

Sample Input #2

10 10
1 2 265 1544 0 1548 4334 9846 58 0
21 0 50 44 2 388 5 0 0 4
170 0 2 1 54 1379 50 3 41 0
310 0 1 0 2163 0 226 26 3 12
151 33 0 9 0 0 0 36 365 2286
0 3 12 3 9 317 645 100 21 4
52 1 569 0 144 0 6 202 25 0
8869 19 2058 1948 1252 1002 7 1750 0 5
0 3 8 29 2 4403 0 0 0 5
0 17 93 9367 159 6 1 216 0 0

Sample Output #2

246

Notes/Hints

Note

Mentioning this problem is prohibited until December 29, 2019, 05:00 JST. If mentioned, compensation may be claimed.

It is okay to announce the total score and certification level after the test, but please do not disseminate information about which problems were solved.

Constraints

• $2 \leq H, W \leq 50$
• $0 \leq A_{i,j} \leq 100,000$
• $ A_{H,1} = A_{H,W} = A_{1,W} = 0 $
• All values in the input are integers.

Sample Explanation 1

It is optimal to develop all squares with a development cost of $ 1 $ yen.

见题面 Input 部分

见题面 Output 部分