A crawler explores an oubliette laid out as a grid of R rows and C columns, starting at the top-left cell and moving on each step to the cell immediately right or immediately below until reaching the bottom-right cell. Each cell holds an integer oil delta: entering it adds that delta (negative drains the lantern, positive refills it) to the lantern's oil. The oil is applied for every cell entered, including the top-left starting cell.
The lantern must never drop below 1 oil: after entering each cell (including the first and last) the oil must be at least 1. The crawler carries a fixed starting amount of oil before entering the top-left cell.
Determine the minimum starting oil (a positive integer) that lets the crawler pick some right/down route and keep the oil at least 1 at every step.
Input format
Line 1: two integers R and C.
Next R lines: each contains C integers, the oil deltas of that row.
Output format
A single integer: the minimum starting oil that allows a valid right/down route.
Constraints
- 1 <= R <= 100
- 1 <= C <= 100
- -1000 <= each oil delta <= 1000