Сарымсақтар 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