Given a 2D integer matrix grid of size m x n, each cell grid[i][j] represents a health effect: negative values decrease health, positive values increase health, and zero leaves health unchanged. Starting at the top-left cell (0,0), you must reach the bottom-right cell (m-1,n-1) by only moving right or down. At any point, if your health drops to zero or below, you fail. Determine the minimum initial health required to guarantee reaching the bottom-right cell alive.
Example 1
Input: [[1, -2, 3], [-4, 5, -6], [7, -8, 9]]
Output: 2
Explanation: The minimum initial health required is 2. One optimal path is (0,0)->(1,0)->(2,0)->(2,1)->(2,2).
Example 2
Input: [[0, 0], [0, 0]]
Output: 1
Explanation: All cells are zero, so minimum initial health is 1.
Example 3
Input: [[-1]]
Output: 2
Explanation: Single cell with -1, so minimum initial health is 2.
Constraints
Case 1
Input: [[2, -3, 4], [-5, 6, -7], [8, -9, 10]]
Expected: 3
Case 2
Input: [[0, -1], [-2, 3]]
Expected: 2
Case 3
Input: [[5]]
Expected: 1
Case 4
Input: [[-10, 5], [3, -2]]
Expected: 11