Сарымсақтар vs. Зомби ойынының су жаңа шыққан жаңартылуында ойыншылар зомби рөлінде ойнау мүмкіндігіне ие болды! bthero және fractal бір-біріне қарама қарсы көптеген раундтар ойнап үлгерді және қазір келесі раундты ойнауға дайындалып жатыр. Жаңа раундта fractal зомби болып ойнайды, ал bthero ойын алаңына сарымсақтарды орналастырады.

Ойын алаңы $n\times m$ өлшеміндегі тордан тұрады. Әрбір $(i,j)$ торкөзінде беріктігі $a_{i,j}$ болатын сарымсақ орналасқан. Сарымсақтың беріктігі — оны жою үшін қанша рет соғу керектігін көрсететін мән.

fractal ойынды бірінші бағанның кез келген торкөзінен $(j=1)$ бастайды және келесі ережелер бойынша қозғалады:

• Егер сарымсақтың беріктігі нөлден үлкен болса $(a_{i,j}>0)$, fractal сол сарымсаққа соққы береді (яғни $a_{i,j}$-ды 1-ге азайтады) және одан кейін жоғарғы $(i-1,j)$ немесе төменгі $(i+1,j)$ торкөздеріне өтеді, егер сондай торкөздер бар болса.

• Егер сарымсақтың беріктігі нөлге тең болса $(a_{i,j}=0)$, fractal оң жағында орналасқан $(i,j+1)$ торкөзіне өтуі керек.

fractal мақсаты ойын алаңынан ең аз қадам саны ішінде толықтай өту, яғни соңғы бағанға $(j=m+1)$ мүмкіндігінше тезірек жетуі керек. fractal ойынның аяқталуы үшін минималды қанша қадам жасау керектігін анықтауға көмектесіңіз!

Енгізу

Кіріс деректерінің бірінші жолында екі бүтін сан $n,m$ берілген — ойын алаңының жолдар саны мен бағандар саны $(2\le n\le 1500,1\le m\le 1500)$.

Келесі $n$ жолда $m$ сан $a_{i,j}$ берілген — $i$-ші жолдағы $j$-ші бағандағы сарымсақтың беріктігі $(0\le a_{i,j}\le {10}^9)$.

Шығару

fractal $(j=m+1)$ бағанына жету үшін минималды қадамдар санын шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

2 3
2 1 4
5 3 5

Жауап 1

17

Енгізу 2

2 4
3 0 0 3
1 0 1 0

Жауап 2

8

Енгізу 3

3 3
3 2 0
2 1 1
0 2 2

Жауап 3

7