Researchers
The latest space expedition to Mars has indeed discovered life forms. Ukrainian astronaut-researchers Yehor Kulvasenko and Petro Kamrabov have found small creatures resembling ordinary Earth mice.
Upon returning to their planetary station after an excursion on the Martian surface, the astronauts witnessed an astonishing sight: Martian "mice" gathered in groups on a rectangular plateau. This plateau had been divided into square cells by an unknown force many millennia ago, as research suggests.
After transmitting the plateau's coordinates to their onboard computer, the scientists received a map in response. This map showed the number of Martian "mice" in each cell and identified which cells were impassable due to lethal radiation levels.
The scientists were positioned in the top right corner of the map.
Realizing that their oxygen supplies were limited, the researchers could only move across the plateau towards the station by going left or down. They decided to traverse the plateau from the top right to the bottom left corner to capture the maximum number of Martian mice without entering cells with high radiation levels. Your task is to help the researchers find the optimal path.
Input Data
The first line of the input contains the dimensions of the plateau, M and N, both of which do not exceed 150. The following M rows each contain N integers that describe the plateau. A non-negative number indicates the number of mice in that cell, while a -1 signifies an impassable cell. All numbers do not exceed 10^5.
Output Data
Determine the maximum number of mice the researchers can catch and output this number on a single line.