EduBrick

K. Маршрут максимальной стоимости

2000 мс · 256 МБ · всё или ничего

В левом верхнем углу таблицы n×mn \times m находится черепашка. В каждой клетке записано число. Черепашка перемещается только вправо или вниз и заканчивает маршрут в правом нижнем углу.

Просуммируем числа во всех клетках, через которые проползла черепашка, включая начальную и конечную. Найдите наибольшее возможное значение этой суммы.

В исходной задаче требовалось вывести ещё и сам маршрут, а маршрутов с одинаковой суммой бывает много. Здесь нужна только сумма; маршрут спрашивают в домашней работе, и там для него зафиксировано правило.

Формат ввода

Первая строка содержит числа nn и mm (1≤n,m≤10001 \le n, m \le 1000).

Следующие nn строк содержат по mm целых чисел от 00 до 100100.

Формат вывода

Одно число — наибольшая возможная сумма.

Примеры

ввод
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
вывод
74
Войдите, чтобы отправлять решения.