Health for the Dungeon

A knight must cross a dungeon laid out as a grid of rooms, from the top-left room to the bottom-right room, moving only right or down. Each room holds a whole number: a negative number is a monster that takes that much health, a positive number is a potion that gives that much, and 0 is an empty room. The first and the last room count too.

The knight's health must stay at least 1 the whole time, including right after entering each room. Write min_health(dungeon) that returns the smallest whole-number starting health that lets the knight reach the bottom-right room alive along some route.

Examples

min_health([[-3, 4], [-6, -2]])                          # returns 4
min_health([[2, -8, 5], [-6, -1, 0], [0, -6, -4]])       # returns 7
min_health([[5]])                                        # returns 1

In the first example the knight goes right, then down: starting with 4, health drops to 1, rises to 5 and ends at 3. The starting health is always at least 1, even in a dungeon without monsters.

Constraints

• The dungeon has 1 to 200 rows and 1 to 200 columns.
• -1000 <= dungeon[r][c] <= 1000