509. Save Princess

0

Hard

In the kingdom of Winterfell, the princess is trapped in a grid located in King's Landing. Her brother, John, has come to rescue her. However, John's health is limited, and he must save his sister. As he traverses the grid, he will encounter cells with soldiers (represented by negative numbers), which will decrease his health, and cells with energy potions (represented by positive numbers), which will increase his health. John's objective is to determine the minimum initial health he must have in order to successfully save the princess. John can only move right or down, and if his health reaches zero, he will die.

Input Format

Two integers, m and n, representing the number of rows and columns in the grid, respectively. The next m lines will each contain n integers to form the grid.

Output Format

Return the minimum initial health that John must have in order to successfully rescue the princess.

Example

Input

3 3 -2 -3 3 -5 -10 1 10 30 -5

Output

7

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
-1000 <= grid[i][j] <= 1000