Problem Description

JOI Kingdom has a vast forest. The forest is rectangular in shape and is divided into a grid of $ H $ squares from north to south and $ W $ squares from east to west. The area from the north $ i $ square and from the west $ j $ square ($1\ ≦\ i\ ≦\ H,\ 1\ ≦\ j\ ≦\ W$) has $ A_{i,j} $ trees. However, the area at the northwest corner has a wood processing factory and no trees, i.e., $ A_{1,1}=0 $.

People can enter areas without trees. Also, people can move to adjacent areas to the east, west, north, or south if those areas do not have trees. Leaving the forest is not possible. JOI wants to carry out a public project in JOI Kingdom by cutting down trees to make it possible to travel between the northwest corner and the southeast corner.

Tree cutting is carried out as follows. Initially, JOI is at the northwest corner where the wood processing factory is located. JOI can move to adjacent areas without trees in $ 1 $ minute. Also, JOI can cut down $ 1 $ tree in $ 1 $ minute from an adjacent area with trees. However, every time a tree is cut down, JOI must transport the tree back to the wood processing factory at the northwest corner. The speed of movement remains the same while transporting trees. While transporting trees, JOI cannot cut down other trees.

Find the minimum time required to cut down trees to meet the conditions. The time to cut down trees is defined as the time until the last cut tree is transported to the wood processing factory.

Input Format

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

$ H $ $ W $ $ A_{1,1} $ $ ... $ $ A_{1,W} $ : $ A_{H,1} $ $ ... $ $ A_{H,W} $

Output Format

Output the minimum time required to cut down trees to meet the conditions in one line.

Sample Input and Output

Sample Input #1

2 3
0 1 2
3 4 5

Sample Output #1

32

Sample Input #2

2 5
0 5 0 0 0
0 0 0 9 1

Sample Output #2

13

Sample Input #3

2 5
0 2 0 0 0
0 0 0 9 1

Sample Output #3

11

Notes/Hints

Constraints

• $1\ ≦\ H\ ≦\ 30$
• $1\ ≦\ W\ ≦\ 30$
• $(H,\ W)\ ≠\ (1,\ 1)$
• $0\ ≦\ A_{i,j}\ ≦\ 10000$ ($1\ ≦\ i\ ≦\ H,\ 1\ ≦\ j\ ≦\ W$)
• $ A_{1,1}=0 $

Subtask 1 \[15 points\]

• $1\ ≦\ H\ ≦\ 5$
• $1\ ≦\ W\ ≦\ 5$

Subtask 2 \[28 points\]

• $A_{i,j}\ ≦\ A_{i,j+1}$ ($1\ ≦\ i\ ≦\ H,\ 1\ ≦\ j\ ≦\ W-1$)
• $A_{i,j}\ ≦\ A_{i+1,j}$ ($1\ ≦\ i\ ≦\ H-1,\ 1\ ≦\ j\ ≦\ W$)

Subtask 3 \[57 points\]

• No additional restrictions.

Sample Explanation 1

Represent the area from the north $ i $ square and from the west $ j $ square as $(i,\ j)$. First, cut down the trees in $(1,\ 2)$. This takes $ 1 $ minute. Then, cut down all the trees in $(1,\ 3)$. Cutting down one tree requires moving from $ (1,1) $ to the east by $ 1 $ square, cutting the tree in $(1,\ 3)$, and returning to $ (1,1) $ by moving west by $ 1 $ square, which takes $ 3 $ minutes. Therefore, this takes $2\ ×\ 3\ =\ 6$ minutes. Next, cut down all the trees in $(2,\ 3)$. Cutting down one tree requires moving from $ (1,1) $ to the east by $ 2 $ squares, cutting the tree in $(2,\ 3)$, and returning to $ (1,1) $ by moving west by $ 2 $ squares, which takes $ 5 $ minutes. Therefore, this takes $5\ ×\ 5\ =\ 25$ minutes. In total, it takes $1\ +\ 6\ +\ 25\ =\ 32$ minutes. Since it is not possible to cut down the trees in a shorter time to meet the conditions, output $ 32 $.

Sample Explanation 2

Only the trees in $(2,\ 5)$ need to be cut down.

Sample Explanation 3

First, cut down the trees in $(1,\ 2)$, then cut down the trees in $(2,\ 5)$.

见题面 Input 部分

见题面 Output 部分