Играта Зајак се игра на една правоаголна табла со M редици и N колони. Полето кое се наоѓа во i-тата редица и j-тата колона на таблата се означува со подредениот пар (i, j).

Играта се игра со повеќе играчи. Секој играч има своја фигура - зајаче чија почетна позиција е во полето (1, 1). Зајачето може да стапне на секое поле од таблата, а може да се случи и повеќе зајачиња да бидат на исто поле во даден момент. Во оваа игра играчите играат еден по друг и секој играч треба во еден круг да изведе две акции (прво скок, па потоа чекор):

1) Скок. Со еден скок зајачето може да скокне во истата редица и во произволна, но друга колона: од поле (i, j) во поле (i, k), каде j<>k.

2) Чекор. Со еден чекор зајачето се движи еден чекор до полето во истата колона, следната редица (за еден поголема редица): од поле (i, j) во поле (i+1, j).

Целта на играта е зајачето да стигне до полето (M, N). Во последниот круг играчот може да ја изведе само акцијата Скок, ако тоа е потребно, во случај кога зајачето е во поле од редицата M, но не се наоѓа во полето (М, N).

Секое зајаче на полињата на кои застанува може да земе моркови. Имено, во секое поле има дадено број на моркови кое секое зајаче може да ги собере стапнувајќи на него. Ако застанат повеќе зајчиња на истото поле сите земаат онолку моркови колку дозволува полето.

Победник ќе биде оној играч чие зајаче ќе стигне од почетокот (1, 1) до крајот (M, N) со најмногу собрани моркови.

Зоки е одличен во оваа игра и тој има стратегија со која секогаш победува и собира максимален број моркови. Вие треба да најдете колку моркови ќе земе зајачето на Зоки во дадена игра.

Влез

Во првиот ред се внесуваат два цели броја M и N, одделени со празно место, со кои се дадени димензиите на правоаголната табла на играта (1 <=M, N <= 1 000). Во следните M линии се дадени N броеви, одделени со по едно празно место. Секој број Zij (1 <= i <= M, 1 <= j <= N) го претставува бројот на моркови кои секое зајаче може да ги земе ако стапне на полето (i, ј) (1 <= Zij <= 255)

Забелешка: За најмногу 60% од поените важи: 1 <=M, N <= 500

Излез

Еден цел број кој означува колку моркови ќе земе зајачето на Зоки.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2 3
10 4 5 
6  6 3

излез
23

влез
2 3
10 4 15 
6  6 3

излез
28

Објаснување за првиот тест пример: Во првиот круг Зоки од полето (1, 1) би скокнал до полето (1, 2), па би направил чекор до (2, 2). Во вториот круг за да стигне до полето (2, 3) потребно е само да скокне до полето (2, 3). Во полињата каде ќе стапне зајачето ќе земе вкупно: 10+4+6+3=23 моркови.

Објаснување за вториот тест пример: Во првиот круг Зоки од полето (1, 1) би скокнал до полето (1, 3) , па би направил чекор до (2, 3). Со ова ќе стигне до крајот во првиот круг, а ќе земе најмногу моркови. Бројот на моркови е: 10 (1,1) + 15 (1,3) + 3 (2,3) =28.