It's Cady's second day at North Shore High, and she's trying to cross the lunchroom to meet her friends, Janis Ian and Damian Leigh.

The lunchroom is an ~n \times m~ grid of square tables. Each table has a "lameness" value depending on the clique of people sitting there. Walking past one side of a table will make Cady gain that amount of lameness. You need to be careful who you're seen with!

Cady starts in the top-left corner of the lunchroom, and wants to get to the bottom-right, where Janis and Damian are, while gaining the minimum possible lameness. For example, if the lunchroom has ~3 \times 3~ tables, with the following lameness values:

Then Cady can minimise her lameness by taking the following path:

1. Move down and get ~2~ lameness.
2. Move right and get ~2+4 = 6~ lameness.
3. Move down and get ~4+1 = 5~ lameness.
4. Move right and get ~1+0 = 1~ lameness.
5. Move down and get ~0+0 = 0~ lameness.
6. Move right and get ~0~ lameness.

So Cady's total lameness is ~2 + 6 + 5 + 1 = 14~, which is the minimum possible in this scenario.

Input

The first line consists of two integers, ~n~ and ~m~ ~(1 \leq n, m \leq 1000)~, indicating that there are ~n~ rows and ~m~ columns of tables in the lunchroom.

The next ~n~ lines consist of ~m~ integers, representing a row of "lameness" values ~l_{i,j}~ ~(0 \leq l_{i,j} \leq 10^8)~ of each table.

Output

Output the minimum amount of lameness Cady can incur, when walking from the top-left of the lunchroom to the bottom-right.

Clarifications

Cady can gain the "lameness" of a table multiple times, if she walks by multiple sides of the table. For example, turning a corner.

Example

Input 1

2 2
1 8
2 1

Output 1

6

Cady can all the way down, then all the way to the right, to reach Janis and Damian with ~6~ lameness.

Input 2

6 4
1 1 1 1
100 100 100 1
1 1 1 1
1 1 1 1
1 100 100 100
1 1 1 1

Output 2

22

Cady can in an S-shaped curve around the ~100~-lameness tables to reach Janis and Damian with ~22~ lameness.

Input 3

3 3
2 7 4
4 1 2
6 0 0

Output 3

14