After finding your friend's secret underground base in Minecraft, you decide on the great move of stealing all their valuables. Just as you finish looting, they unexpectedly log on. It's time to get out of there by mining out as fast as possible before they catch you!

Some blocks in your path can be mined faster than others, so certain paths may be faster. As your character is ~2~ blocks tall, you'll have to mine a path where a ~2~ block tall player will be able to pass through.

Given a section of blocks you can make a tunnel through, what is the least amount of time it will take to make a tunnel from the left side of the blocks to the right side of the blocks?

Input

The first line will consist of 2 integers ~h~ ~(2 \leq h \leq 10^{3})~ and ~w~ ~(1 \leq w \leq 10^{3})~, the height and width of the section of blocks you can mine through.

The next ~h~ lines will contain each ~w~ integers ~x_{i,j}~ ~(1 \leq x_{i,j} \leq 10^{5})~, representing the amount of time in seconds it takes to mine the corresponding block

Output

Print the least amount of time it will take to make a tunnel from the left to the right side of the blocks that a ~2~ block tall character will be able to pass through.

Clarifications

You may not rotate the character. Assume that the character will be able to jump and drop any amount of blocks they wish.

Examples

Input 1

4 6
84 99 88 75 11 13
10 11 75 81 11 13
13 21 10 19 10 94
77 15 10 10 31 93

Output 1

208

Explanation

The least amount of time taken to create a tunnel will be the following tunnel, which takes 208 seconds to mine. A 2 block tall character will be able to pass through the tunnel.

84 99 88 75  x  x
 x  x 75 81  x  x
 x  x  x  x  x 94
77  x  x  x  x 93