Исследователи
Очередная космическая экспедиция на Марс обнаружила там формы жизни. Украинские космонавты-исследователи Егор Кулвасенко и Пётр Камрабов нашли маленьких существ, напоминающих земных мышей. Возвращаясь на планетарную станцию после одной из вылазок на поверхность, они стали свидетелями удивительного зрелища: марсианские «мыши» собрались в группы на прямоугольном плато, которое, как показали исследования, неизвестная сила разбила на квадратные клеточки много тысячелетий назад.
Передав координаты плато бортовому компьютеру, учёные получили его карту. На карте указано, сколько марсианских «мышей» находится в каждой клеточке, а также какие клеточки непроходимы из-за смертельного уровня радиации.
Учёные находятся в правом верхнем углу карты.
Исследователи осознали, что их запасы кислорода ограничены, поэтому они могут двигаться по плато только в направлении станции: влево или вниз. Они решили пройти от правого верхнего угла к левому нижнему, чтобы поймать как можно больше марсианских мышей, избегая клеточек с повышенной радиацией. Помогите исследователям найти оптимальный маршрут.
Входные данные
Первая строка файла содержит размеры плато M и N, которые не превышают 150. Следующие M строк содержат по N целых чисел, описывающих плато. Если число неотрицательное, оно указывает количество мышей в данной клеточке. Если число -1, клеточка считается непроходимой. Все числа не превышают 10^5.
Выходные данные
Определите максимальное количество мышей, которых могут поймать исследователи, и выведите это число в единственной строке выходного файла.