Minimum Cells Removal for Energy Preservation

You are given an \(n \times n\) grid where each cell contains an integer value representing its effect on Polycarp's energy. Polycarp starts at the top-left corner with an initial energy of 0 and must reach the bottom-right corner by moving either right or down at each step.

When Polycarp enters a cell with value \(g\), his energy is updated as follows:

If the cell's value is negative (i.e. \(g < 0\)), then Polycarp "removes" that cell, which incurs a cost of 1 removal. The goal is to choose a path from the top-left to the bottom-right corner that minimizes the total number of cells removed, while ensuring that his energy remains non-negative throughout his journey.

It is guaranteed that a valid path exists. Calculate the minimum number of cells Polycarp needs to remove.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(n\) representing the size of the grid.
• The following \(n\) lines each contain \(n\) space-separated integers representing the grid values.

outputFormat

Output to standard output (stdout) a single integer denoting the minimum number of cells that need to be removed so that Polycarp can travel from the top-left to the bottom-right corner without his energy dropping below zero.

3
1 -2 3
-4 5 -1
2 -3 4

2