Ви граєте в матричну гру з такими налаштуваннями та правилами:
Вам дається матриця \(A\) розмірності \(n \times m\). Кожна клітинка матриці містить цілі числа. Коли гравець проходить через клітинку, його рахунок збільшується на число, записане в цій клітинці, і число в клітинці стає рівним 0. Якщо число у клітинці від'ємне, то кількість балів зменшиться на це число.
Гравець починає гру з будь-якої клітинки в першому ряду і може рухатися вліво, вправо або вниз.
Гра закінчується, коли гравець досягає останнього ряду і зупиняється.
Який максимальний бал зможе отримати гравець.
Формат вхідних даних
Перший рядок вхідного потоку містить цілі числа \(n,m\) (\(1 \le n \times m \le 4 \times 10^6\))
Наступні \(n\) рядків містять по \(m\) цілих чисел - елементи \(A_{ij}\) (\(-250 \le A_{ij} \le 250\)) матриці \(A\). Числа у рядках розділяються пропуском.
Формат вихідних даних
У вихідний потік вивести максимальний бал гравця.
Приклад вхідних даних
4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20
Приклад вихідних даних
37
Приклад вхідних даних
10 1
1
2
3
4
5
6
7
8
9
10
Приклад вихідних даних
55
Коментарі