Dominic Toretto and Brian O’Connor and going head to head in the race of their lives!

Brian wants to win at all costs. He has raced on the track before, and knows that the terrain varies very frequently, hence it is faster to drive through some of the parts than the others.

Consider the road to be divided into $n$ strips (by length) and $m$ lanes (by width). Each segment of road takes a different amount of time to be travelled. The time taken on each segment is given in the form of a matrix of dimensions n*m.

Brian starts at the first strip, and can start from any lane. As he moves forward, he can 1) change to the lane on the immediate left 2) change to the lane on his immediate right 3) stay on the same lane. Note that Brian must keep moving forward, hence he cannot stay on the same strip. He can only change between lanes which are adjacent to his current position.

Brian, in his classic Skyline GTR, wants to defeat Dom by all means. Can you figure out the fastest time in which he can finish the race?

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

INPUT:

The first line contains two integers, $n$ and $m$, the number of strips and the number of lanes respectively. The next $n$ lines contain $m$ integers, the time taken on each segment.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

OUTPUT:

Output the minimum time taken by Brian to finish the race.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

CONSTRAINTS:

${1 \le n,m \le 10^3, 1 \le seg[i][j] \le 10^3}$