4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Есеп В. Витя - тасбақа-ниндзя

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Витя жаңа тасбақа-ниндзялар тобының мүшесі болғысы келеді. Оған ең басты сынақты өту керек - Донателлоның берген есебін шығару. Донателло Витяға $n$ қатардан және $m$ бағанадан тұратын кесте береді. Кестенің әр торында бір бүтін сан берілген. Басында кестенің сол төменгі бұрышында фишка тұр. Фишканы бір тор төмен немесе оңға жылжытуға болады. Фишка астыңғы оң бұрышта болмағанынша жылжытады. Фишка өткен тордағы сандардың қосындысы жолдың нәтижесі деп аталады(бастапқы және соңғы торлар да саналады). Витяға нәтижесі ең үлкен болатын жол табу керек. Леонардо бұл сынақты Витя үшін өте оңай деп ойлайды . Сол себептен ол есепті қиындатуды шешті. Фишканы жылжытпас бұрын, Витя Леонарданы таблицада бірнеше (мүмкін 0) вертикаль және горизанталь кесуді сұрай алады . Торлардың шетінен ғана кесуге болады және Леонарда кескенде таблица басынан соңына дейін кесіледі. Нәтижесінде, кесте бірнеше бөлімге бөлінеді. Енді фишка кестенің үстінгі сол бұрышындағы бөлімде және оны төменгі немесе оң жақтағы бөлімге ауыстыруға болады, ол астыңғы оң бұрышта болмағанша. Осындай жолдын нәтижесі деп, барлық өткен бөлімдегі торларда жазылған сандардың қосындысын айтамыз. Нәтижені ең үлкен қылатындай кестені кесіп, фишканы жүргізетін жолды табыңыз.

Формат входного файла

Бірінші жолда $n$ және $m$ ($1 <= n <= 1000$, $1 <= m <= 50$). Келесі $n$ жолда $m$ бүтін сан -- $j$-ші сан $i$-ші қатарда $a_{i, j}$ ($-10^{9} <= a_{i, j} <= 10^9$) кестедеші $i$-ші қатарда $j$-ші бағандағы кестедегі жазылған сан.

Формат выходного файла

Есептің жауабың шығарыңыз.

Система оценки

Есеп $8$ бөлімнен тұрады:

1. Мысалдар. $0$ ұпайға бағаланады.
2. $a_{i, j} > 0$. $5$ ұпайға бағаланады..
3. $a_{i, j} < 0$. $12$ ұпайға бағаланады.
4. $n = 2$. $10$ ұпайға бағаланады.
5. $n, m <= 10$. $10$ ұпайға бағаланады.
6. $n, m <= 40$. $20$ ұпайға бағаланады.
7. $n <= 100$, $m <= 50$. $21$ ұпайға бағаланады.
8. Ешқандай қосымша шектеу жоқ. $22$ ұпайға бағаланады.

Примеры:

Вход

2 2
2000 600
0 4

Ответ

2604

Вход

4 5
4 23 -10 -2 3
0 1 7 -3 0
2 3 -3 30 1
4 -17 8 0 5

Ответ

78

Замечание

Екінші мысал.

( Rauan Omarov )