Minimum Starting Value to Cross a Grid

You are given an integer grid grid with m rows and n columns.

You walk from the top-left cell to the bottom-right cell. From a cell you may step one cell right or one cell down, and nothing else.

You keep a running total. Before the walk starts you set it to a starting value of your choice, which must be a positive integer. Entering a cell adds that cell's value to the running total, and the top-left cell counts as entered at the very start.

A starting value works if some walk keeps the running total at 1 or more after every cell it enters, including the top-left cell and the bottom-right cell.

Return the smallest starting value that works.

Examples

Example 1

Input: grid = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: With a starting value of 7, the walk right, right, down, down enters cells -2, -3, 3, 1, -5, so the running total goes 5, 2, 5, 6, 1. It never drops below 1.
A starting value of 6 sends that same walk to 4, 1, 4, 5, 0, and no other walk survives 6 either.

Example 2

Input: grid = [[0]]
Output: 1
Explanation: The walk is a single cell that adds 0. A starting value of 1 gives a running total of 1, and the starting value has to be positive, so 1 is the smallest.