A player enters a grid of rooms at the top-left room. The goal is in the bottom-right room. From any room, the player can only move one step right or one step down.
The grid dungeon has a number in every room:
- A negative number means the player loses that much health in this room.
- Zero means nothing happens.
- A positive number means the player gains that much health.
The player's health must stay above 0 at all times. This also holds right after entering the first room and the last room, once that room's number is applied.
Return the smallest starting health that lets the player reach the bottom-right room.
Examples
Example 1:
Input: dungeon = [[-1,-2],[-3,4]]
Output: 4
Explanation: Go right, then down. Start with 4: health goes 3, then 1, then 5. Starting with 3 would drop to 0.
Example 2:
Input: dungeon = [[5]]
Output: 1
Explanation: The room is good for the player, but health must still start above 0, so 1 is enough.
Example 3:
Input: dungeon = [[2,-5,1],[-3,4,-6],[0,-2,3]]
Output: 2
Explanation: Go down, right, down, right. Start with 2: health goes 4, 1, 5, 3, 6 and never reaches 0. Starting with 1 fails.