Dungeon Game: Rescue the Princess

You are given a dungeon represented as an m x n grid. Each cell in the grid contains an integer representing either a health potion (positive value), a monster attack (negative value), or no effect (zero). The knight starts at the top-left cell and needs to reach the bottom-right cell where the princess is held captive. Along the way, the knight can only move either right or down. In order to survive, the knight's health must always remain positive.

Your task is to calculate the minimum initial health the knight must have so that he can rescue the princess.

The problem can be formulated as follows. Let \( dungeon[i][j] \) be the value in cell \( (i, j) \). If the knight enters a cell with a negative number, he loses health; if the number is positive, he gains health. The knight dies if his health drops to 0 or below. You must determine the minimum starting health such that the knight can travel from the top-left to the bottom-right, maintaining his health strictly positive at each step.

Note: The answer is guaranteed to be at least 1.

inputFormat

The first line contains two integers m and n, representing the number of rows and columns in the dungeon grid respectively.

This is followed by m lines, each containing n space-separated integers representing the dungeon grid.

It is guaranteed that m, n \( \geq 1 \).

outputFormat

Output a single integer, which is the minimum initial health the knight must start with so that he can rescue the princess.

3 3
-2 -3 3
-5 -10 1
10 30 -5

7