Dungeon Game

A knight starts at the top-left corner of a dungeon and must rescue a princess at the bottom-right corner. The knight can only move right or down.

Each cell contains an integer. A positive value gives health, a negative value removes health, and zero does nothing. The knight's health changes on entering a cell, including the starting cell and the princess's cell.

The knight dies if health drops to 0 or below at any point. Find the minimum initial health needed to reach the princess alive.

Input & Output

Input

dungeon — the dungeon grid, where each cell adds or removes health

Output

the minimum initial health that lets the knight reach the bottom-right cell without health ever dropping to 0

Example

Input

dungeon = [[-2,-3,3], [-5,-10,1], [10,30,-5]]

Output

Explanation

Starting with 7 health and taking right, right, down, down, the knight visits -2, -3, 3, 1, -5, so health runs 7 → 5 → 2 → 5 → 6 → 1 and never reaches 0. Starting with 6 fails on every path.

Example

Input

dungeon = [[0,-10,30], [-1,-1,-1]]

Output

Explanation

Going down first and then right twice costs 0, -1, -1, -1, so 4 health is enough. The top route through 30 ends with far more health, but it passes the -10 cell first and needs 11 to survive it. The path that collects the most is not the path that needs the least to start.

Constraints

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

Dungeon Game

Try it yourself