Рабочее место участника

Есть прямоугольное поле размером `N\ times\ M`, разбитое на клетки единичного размера. В некоторых клетках этого поля расположены препятствия, и на них нельзя попасть, а для каждой из остальных клеток известно количество золота, которое в ней находится. У вас есть три робота, изначально они находятся в левом верхнем углу поля, и все они должны добраться до правого нижнего угла поля. За один ход каждый робот может сдвинуться на одну клетку вправо или на одну клетку вниз, если он при этом не выйдет за пределы поля и не попадет на клетку с препятствием. Находясь на определенной клетке, робот забирает из нее все золото. Взятое золото в клетке не восстанавливается, и другие роботы там уже ничего не получат. На одной клетке могут находиться несколько роботов. Когда все роботы добираются в правый нижний угол, подсчитывается суммарное количество золота, собранного ими. Требуется так провести роботов по полю, чтобы максимизировать это суммарное количество золота. Гарантируется, что роботов можно провести из левого верхнего в правый нижний угол.

В первой строке входного файла содержится два целых числа `N` и `M` (`2≤N,\ M≤50`). Далее следуют `N` строк, в каждой из которых содержится `M` целых чисел в диапазоне от `-1` до 1000 (числа в строке отделяются пробелами). Число, находящееся в `i`-й строке на `j`-м месте, равно количеству золота в соответствующей клетке поля или `-1`, если в этой клетке находится препятствие. В левом верхнем и в правом нижнем углах поля всегда находится ноль единиц золота.

Вывести единственную строку, содержащую максимальное суммарное количество золота, которое могут собрать три робота.

3 3
0 5 7
3 8 6
9 -1 0

29

4 5
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 0

164