1217. Dungeon Game — Minimum Health

A knight starts at the top-left of a dungeon grid and must reach the princess at the bottom-right, moving only right or down. Each cell changes his health by its value, and his health must stay at least 1 at all times. Return the minimum initial health required. The input is JSON {dungeon}.

Input: JSON {dungeon}.

Output: Integer — the minimum initial health.

Examples

Input: {"dungeon":[[-2,-3,3],[-5,-10,1],[10,30,-5]]}
Output: 7
Explanation: Seven health suffices on the optimal path.

Input: {"dungeon":[[0]]}
Output: 1
Explanation: Minimum health is 1.

Input: {"dungeon":[[-5]]}
Output: 6
Explanation: Need 6 to survive -5.

Constraints

• 1<=rows,cols<=200

Asked by