Given a grid of size M*N with each cell consisting of an integer which represents points. We can move across a cell only if we have positive points. Whenever we pass through a cell, points in that cell are added to our overall points, the task is to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :
 
1. From a cell (i, j) we can move to (i + 1, j) or (i, j + 1).
2. We cannot move from (i, j) if your overall points at (i, j) are <= 0.
3. We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.
Example 1:
Input: M = 3, N = 3 
       arr[][] = {{-2,-3,3}, 
                  {-5,-10,1}, 
                  {10,30,-5}}; 
Output: 7
Explanation: 7 is the minimum value to
reach the destination with positive
throughout the path. Below is the path.
(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)
We start from (0, 0) with 7, we reach
(0, 1) with 5, (0, 2) with 2, (1, 2)
with 5, (2, 2) with and finally we have
1 point (we needed greater than 0 points
at the end).
Example 2:
Input: M = 3, N = 2
       arr[][] = {{2,3}, 
                  {5,10}, 
                  {10,30}}; 
Output: 1
Explanation: Take any path, all of them 
are positive. So, required one point 
at the start
Your Task:  
You don't need to read input or print anything. Complete the function minPoints() which takes N, M and 2-d vector as input parameters and returns the integer value
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ N ≤ 10^{3}

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)

Starter code:
#User function Template for python3
class Solution:
	def minPoints(self, points, M, N):
		# code here

Solutions:
class Solution:

	def minPoints(self, points, M, N):
		dp = [[0 for _ in range(N)] for _ in range(M)]
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				if i == M - 1 and j == N - 1:
					dp[i][j] = max(1 - points[i][j], 1)
				elif i == M - 1:
					dp[i][j] = max(dp[i][j + 1] - points[i][j], 1)
				elif j == N - 1:
					dp[i][j] = max(dp[i + 1][j] - points[i][j], 1)
				else:
					dp[i][j] = max(min(dp[i + 1][j] - points[i][j], dp[i][j + 1] - points[i][j]), 1)
		return dp[0][0]


class Solution:

	def minPoints(self, points, m, n):
		dp = []
		for i in range(m):
			temp = []
			for j in range(n):
				temp.append(0)
			dp.append(temp)
		if points[m - 1][n - 1] < 1:
			dp[m - 1][n - 1] = 1 - points[m - 1][n - 1]
		else:
			dp[m - 1][n - 1] = 1
		for i in range(m - 2, -1, -1):
			current = points[i][n - 1]
			if current < 0:
				current = dp[i + 1][n - 1] - current
			else:
				current = max(1, dp[i + 1][n - 1] - points[i][n - 1])
			dp[i][n - 1] = current
		for i in range(n - 2, -1, -1):
			current = points[m - 1][i]
			if current < 0:
				current = dp[m - 1][i + 1] - current
			else:
				current = max(1, dp[m - 1][i + 1] - points[m - 1][i])
			dp[m - 1][i] = current
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - points[i][j], 1)
		return dp[0][0]


class Solution:

	def minPoints(self, points, M, N):
		(N, M) = (len(points), len(points[0]))
		dp = [[0 for _ in range(M)] for _ in range(N)]
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if i == N - 1 and j == M - 1:
					temp = points[i][j]
					dp[i][j] = 0 if temp >= 0 else temp
				elif i == N - 1 and j != M - 1:
					temp = points[i][j] + dp[i][j + 1]
					dp[i][j] = 0 if temp >= 0 else temp
				elif i != N - 1 and j == M - 1:
					temp = points[i][j] + dp[i + 1][j]
					dp[i][j] = 0 if temp >= 0 else temp
				elif i != N - 1 and j != M - 1:
					temp = max(points[i][j] + dp[i + 1][j], points[i][j] + dp[i][j + 1])
					dp[i][j] = 0 if temp >= 0 else temp
		ans = abs(dp[0][0]) + 1
		return ans


class Solution:

	def minPoints(self, points, M, N):
		result = [[0 for i in range(N)] for j in range(M)]
		if points[M - 1][N - 1] > 0:
			result[M - 1][N - 1] = 1
		else:
			result[M - 1][N - 1] = abs(points[M - 1][N - 1]) + 1
		for i in range(M - 2, -1, -1):
			result[i][N - 1] = max(result[i + 1][N - 1] - points[i][N - 1], 1)
		for i in range(N - 2, -1, -1):
			result[M - 1][i] = max(result[M - 1][i + 1] - points[M - 1][i], 1)
		for i in range(M - 2, -1, -1):
			for j in range(N - 2, -1, -1):
				min_points = min(result[i + 1][j], result[i][j + 1])
				result[i][j] = max(min_points - points[i][j], 1)
		return result[0][0]


class Solution:

	def minPoints(self, points, R, C):
		dp = [[0 for x in range(C)] for y in range(R)]
		(m, n) = (R, C)
		if points[m - 1][n - 1] > 0:
			dp[m - 1][n - 1] = 1
		else:
			dp[m - 1][n - 1] = abs(points[m - 1][n - 1]) + 1
		for i in range(m - 2, -1, -1):
			dp[i][n - 1] = max(dp[i + 1][n - 1] - points[i][n - 1], 1)
		for i in range(n - 2, -1, -1):
			dp[m - 1][i] = max(dp[m - 1][i + 1] - points[m - 1][i], 1)
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				min_points_on_exit = min(dp[i + 1][j], dp[i][j + 1])
				dp[i][j] = max(min_points_on_exit - points[i][j], 1)
		return dp[0][0]


import math

class Solution:

	def minPoints(self, a, n, m):
		dp = [[math.inf] * m for i in range(n)]
		dp[n - 1][m - 1] = 1 + abs(a[n - 1][m - 1]) if a[n - 1][m - 1] < 0 else 1

		def solve(i, j, dp):
			if i > n - 1 or j > m - 1:
				return math.inf
			if dp[i][j] != math.inf:
				return dp[i][j]
			x = min(solve(i + 1, j, dp), solve(i, j + 1, dp))
			if a[i][j] < 0:
				dp[i][j] = x + abs(a[i][j])
			elif a[i][j] >= x:
				dp[i][j] = 1
			else:
				dp[i][j] = x - a[i][j]
			return dp[i][j]
		dp[0][0] = solve(0, 0, dp)
		return dp[0][0] if dp[0][0] else 1


def f(A, N, M, x, y, dp):
	if x >= N or y >= M:
		return 1000000000.0
	if x == N - 1 and y == M - 1:
		if A[x][y] <= 0:
			return 1 + abs(A[x][y])
		else:
			return 1
	if dp[x][y] != -1:
		return dp[x][y]
	down = f(A, N, M, x + 1, y, dp)
	right = f(A, N, M, x, y + 1, dp)
	ans = min(down, right) - A[x][y]
	if ans <= 0:
		ans = 1
	dp[x][y] = ans
	return ans

class Solution:

	def minPoints(self, points, M, N):
		dp = [[-1 for i in range(N + 1)] for i in range(M + 1)]
		ans = 0
		try:
			ans = f(points, M, N, 0, 0, dp)
		except Exception as e:
			print(e)
		return ans


class Solution:

	def minPoints(self, points, m, n):
		points[m - 1][n - 1] = min(points[m - 1][n - 1], 0)
		for i in range(m - 2, -1, -1):
			points[i][n - 1] = min(points[i][n - 1] + points[i + 1][n - 1], 0)
		for i in range(n - 2, -1, -1):
			points[m - 1][i] = min(points[m - 1][i] + points[m - 1][i + 1], 0)
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				points[i][j] = min(0, points[i][j] + max(points[i + 1][j], points[i][j + 1]))
		return abs(points[0][0]) + 1


import sys

class Solution:

	def minPoints(self, points, M, N):
		t = [[-1 for i in range(N + 1)] for j in range(M + 1)]
		y = self.fn(0, 0, M, N, points, t)
		return y

	def fn(self, i, j, m, n, grid, t):
		if i >= m or j >= n:
			return sys.maxsize
		if i == m - 1 and j == n - 1:
			if grid[i][j] <= 0:
				return abs(grid[i][j]) + 1
			else:
				return 1
		if t[i][j] != -1:
			return t[i][j]
		dir1 = self.fn(i + 1, j, m, n, grid, t)
		dir2 = self.fn(i, j + 1, m, n, grid, t)
		mincost = min(dir1, dir2) - grid[i][j]
		if mincost <= 0:
			t[i][j] = 1
		else:
			t[i][j] = mincost
		return t[i][j]


class Solution:

	def minPoints(self, points, m, n):
		dp = []
		for i in range(m + 1):
			dp.append([10 ** 9] * (n + 1))
		dp[m - 1][n] = 1
		dp[m][n - 1] = 1
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				x = min(dp[i + 1][j], dp[i][j + 1]) - points[i][j]
				if x <= 0:
					dp[i][j] = 1
				else:
					dp[i][j] = x
		return dp[0][0]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def minPoints(self, points, N, M):
		dp = [[-1 for i in range(M + 1)] for j in range(N + 1)]

		def recursive(points, dp, N, M, i=0, j=0):
			if i >= N or j >= M:
				return float('inf')
			if i == N - 1 and j == M - 1:
				if points[i][j] <= 0:
					return abs(points[i][j] - 1)
				else:
					return 1
			if dp[i][j] != -1:
				return dp[i][j]
			op1 = recursive(points, dp, N, M, i + 1, j)
			op2 = recursive(points, dp, N, M, i, j + 1)
			dp[i][j] = min(op1, op2) - points[i][j]
			if dp[i][j] <= 0:
				dp[i][j] = 1
			return dp[i][j]
		return recursive(points, dp, N, M)


class Solution:

	def minPoints(self, points, M, N):
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				if i == M - 1 and j == N - 1:
					if points[i][j] > 0:
						points[i][j] = 0
				elif i == M - 1:
					x = points[i][j] + points[i][j + 1]
					points[i][j] = min(0, x)
				elif j == N - 1:
					x = points[i][j] + points[i + 1][j]
					points[i][j] = min(0, x)
				else:
					x = points[i][j] + max(points[i][j + 1], points[i + 1][j])
					points[i][j] = min(0, x)
		return abs(points[0][0]) + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n) = input().split()
		(m, n) = (int(m), int(n))
		points = []
		for _ in range(m):
			temp = [int(x) for x in input().split()]
			points.append(temp)
		ob = Solution()
		ans = ob.minPoints(points, m, n)
		print(ans)


import sys

class Solution:

	def minPoints(self, dungeon, m, n):
		memo = [[-1 for _ in range(n)] for i in range(m)]
		return self.recursion(dungeon, 0, 0, memo)

	def recursion(self, grid, i, j, memo):
		m = len(grid)
		n = len(grid[0])
		if i == m - 1 and j == n - 1:
			return 1 if grid[i][j] >= 0 else -grid[i][j] + 1
		if i == m or j == n:
			return sys.maxsize
		if memo[i][j] != -1:
			return memo[i][j]
		res = min(self.recursion(grid, i, j + 1, memo), self.recursion(grid, i + 1, j, memo)) - grid[i][j]
		memo[i][j] = 1 if res <= 0 else res
		return memo[i][j]


class Solution:

	def minPoints(self, grid, M, N):
		(m, n) = (len(grid), len(grid[0]))
		dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
		dp[m][n - 1] = 1
		dp[m - 1][n] = 1
		for r in range(m - 1, -1, -1):
			for c in range(n - 1, -1, -1):
				need = min(dp[r + 1][c], dp[r][c + 1]) - grid[r][c]
				dp[r][c] = 1 if need <= 0 else need
		return dp[0][0]


class Solution:

	def minPoints(self, grid, n, m):
		t = [[0 for i in range(m)] for j in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if i == n - 1 and j == m - 1:
					if grid[i][j] < 0:
						t[i][j] = abs(grid[i][j]) + 1
					else:
						t[i][j] = 1
				elif i == n - 1:
					t[i][j] = max(t[i][j + 1] - grid[i][j], 1)
				elif j == m - 1:
					t[i][j] = max(t[i + 1][j] - grid[i][j], 1)
				else:
					t[i][j] = max(min(t[i + 1][j], t[i][j + 1]) - grid[i][j], 1)
		return t[0][0]


class Solution:

	def minPoints(self, points, M, N):
		d = [[0 for i in range(N)] for j in range(M)]
		d[M - 1][N - 1] = 0
		if points[M - 1][N - 1] < 0:
			d[M - 1][N - 1] = points[M - 1][N - 1]
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				if i == M - 1 and j == N - 1:
					continue
				if i + 1 < M and j + 1 < N:
					d[i][j] = points[i][j] + max(d[i + 1][j], d[i][j + 1])
					if d[i][j] > 0:
						d[i][j] = 0
				elif i + 1 < M:
					d[i][j] = points[i][j] + d[i + 1][j]
					if d[i][j] > 0:
						d[i][j] = 0
				elif j + 1 < N:
					d[i][j] = points[i][j] + d[i][j + 1]
					if d[i][j] > 0:
						d[i][j] = 0
		return abs(d[0][0]) + 1


class Solution:

	def minPoints(self, l, n, m):
		n = len(l)
		m = len(l[0])
		dp = [[0 for _ in range(m)] for _ in range(n)]
		dp[-1][-1] = min(0, l[-1][-1])
		for i in range(n - 2, -1, -1):
			dp[i][-1] = min(0, dp[i + 1][-1] + l[i][-1])
		for i in range(m - 2, -1, -1):
			dp[-1][i] = min(0, dp[-1][i + 1] + l[-1][i])
		for i in range(n - 2, -1, -1):
			for j in range(m - 2, -1, -1):
				dp[i][j] = min(0, l[i][j] + max(dp[i + 1][j], dp[i][j + 1]))
		return 1 - dp[0][0]


import sys

class Solution:

	def minPoints(self, points, M, N):
		return dp_mp2reach_destination(points)

def _dp_mp2reach_destination(grid, rind, cind, r_length, c_length, dp_matrix):
	if rind >= r_length or cind >= c_length:
		return sys.maxsize
	if dp_matrix[rind][cind] != -1:
		return dp_matrix[rind][cind]
	if rind == r_length - 1 and cind == c_length - 1:
		return 1 if grid[rind][cind] >= 0 else abs(grid[rind][cind]) + 1
	min_value = min(_dp_mp2reach_destination(grid, rind, cind + 1, r_length, c_length, dp_matrix), _dp_mp2reach_destination(grid, rind + 1, cind, r_length, c_length, dp_matrix))
	dp_matrix[rind][cind] = max(min_value - grid[rind][cind], 1)
	return dp_matrix[rind][cind]

def dp_mp2reach_destination(grid):
	row_length = len(grid)
	col_length = len(grid[0])
	dp_matrix = [[-1 for i in range(col_length + 1)] for j in range(row_length + 1)]
	min_points = _dp_mp2reach_destination(grid, 0, 0, row_length, col_length, dp_matrix)
	return min_points


class Solution:

	def minPoints(self, points, n, m):
		inf = float('inf')
		dp = [[0 for i in range(m)] for j in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if i == n - 1 and j == m - 1:
					if points[n - 1][m - 1] > 0:
						dp[n - 1][m - 1] = 1
					else:
						dp[n - 1][m - 1] = abs(points[n - 1][m - 1]) + 1
				elif i == n - 1:
					dp[i][j] = max(1, dp[i][j + 1] - points[i][j])
				elif j == m - 1:
					dp[i][j] = max(1, dp[i + 1][j] - points[i][j])
				else:
					dp[i][j] = max(1, min(dp[i][j + 1], dp[i + 1][j]) - points[i][j])
		return dp[0][0]


class Solution:

	def minPoints(self, points, M, N):
		(r, c, grid) = (M, N, points)
		dp = [[0 for i in range(c)] for j in range(r)]
		if grid[r - 1][c - 1] < 0:
			dp[r - 1][c - 1] = 1 - grid[r - 1][c - 1]
		else:
			dp[r - 1][c - 1] = 1
		for i in range(c - 2, -1, -1):
			dp[r - 1][i] = max(1, dp[r - 1][i + 1] - grid[r - 1][i])
		for i in range(r - 2, -1, -1):
			dp[i][c - 1] = max(1, dp[i + 1][c - 1] - grid[i][c - 1])
		for i in range(r - 2, -1, -1):
			for j in range(c - 2, -1, -1):
				dp[i][j] = max(1, min(dp[i][j + 1], dp[i + 1][j]) - grid[i][j])
		return dp[0][0]


class Solution:

	def minPoints(self, points, M, N):
		k = max(M, N)
		dp = [[-1] * (k + 1) for i in range(k + 1)]
		return self.helperFunction(points, M, N, 0, 0, dp)

	def helperFunction(self, points, M, N, x, y, dp):
		if x == M - 1 and y == N - 1:
			if points[x][y] <= 0:
				return 1 + abs(points[x][y])
			else:
				return 1
		if x == M or y == N:
			return float('inf')
		if dp[x][y] != -1:
			return dp[x][y]
		down = self.helperFunction(points, M, N, x + 1, y, dp)
		left = self.helperFunction(points, M, N, x, y + 1, dp)
		res = min(down, left) - points[x][y]
		if res <= 0:
			dp[x][y] = 1
		else:
			dp[x][y] = res
		return dp[x][y]


import sys

class Solution:

	def minPoints(self, points, M, N):
		dp = [[-1] * N for _ in range(M)]

		def solve(i, j):
			if i == M - 1 and j == N - 1:
				return -1 * points[i][j] + 1 if points[i][j] <= 0 else 1
			if i > M - 1 or j > N - 1:
				return sys.maxsize
			if dp[i][j] != -1:
				return dp[i][j]
			right = solve(i, j + 1)
			down = solve(i + 1, j)
			minHealth = min(right, down) - points[i][j]
			if minHealth <= 0:
				dp[i][j] = 1
			else:
				dp[i][j] = minHealth
			return dp[i][j]
		return solve(0, 0)


class Solution:

	def minPoints(self, points, n, m):
		dp = [[float('inf') for j in range(m + 1)] for i in range(n + 1)]
		dp[n][m - 1] = 1
		dp[n - 1][m] = 1
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				minPoints = min(dp[i + 1][j], dp[i][j + 1]) - points[i][j]
				dp[i][j] = 1 if minPoints <= 0 else minPoints
		return dp[0][0]


from collections import deque

class Solution:

	def minPoints(self, points, M, N):
		dp = [[0 for i in range(N)] for j in range(M)]
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				if i == M - 1 and j == N - 1:
					if points[i][j] > 0:
						dp[i][j] = 1
					else:
						dp[i][j] = abs(points[i][j]) + 1
				elif j == N - 1:
					dp[i][j] = max(dp[i + 1][j] - points[i][j], 1)
				elif i == M - 1:
					dp[i][j] = max(dp[i][j + 1] - points[i][j], 1)
				else:
					dp[i][j] = max(min(dp[i][j + 1], dp[i + 1][j]) - points[i][j], 1)
		return abs(dp[0][0])


class Solution:

	def minPoints(self, points, M, N):
		dp = [[10 ** 9] * (N + 1) for i in range(M + 1)]
		dp[M - 1][N] = 1
		dp[M][N - 1] = 1
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - points[i][j], 1)
		return dp[0][0]


class Solution:

	def minPoints(self, a, r, c):
		dp = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r - 1, -1, -1):
			for j in range(c - 1, -1, -1):
				if i == r - 1 and j == c - 1:
					dp[i][j] = max(1 - a[i][j], 1)
				elif i == r - 1:
					dp[i][j] = max(dp[i][j + 1] - a[i][j], 1)
				elif j == c - 1:
					dp[i][j] = max(dp[i + 1][j] - a[i][j], 1)
				else:
					dp[i][j] = max(min(dp[i + 1][j] - a[i][j], dp[i][j + 1] - a[i][j]), 1)
		return dp[0][0]


class Solution:

	def minPoints(self, points, M, N):
		min_st_cost = [[float('inf')] * N for i in range(M)]
		min_st_cost[M - 1][N - 1] = abs(points[M - 1][N - 1]) if points[M - 1][N - 1] < 0 else 0
		for i in range(M - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				neighbours = [(i - 1, j), (i, j - 1)]
				curr_coins = min_st_cost[i][j]
				for neighbour in neighbours:
					(curr_i, curr_j) = neighbour
					if curr_i < 0 or curr_j < 0:
						continue
					new_coins = curr_coins - points[curr_i][curr_j]
					if new_coins < 0:
						new_coins = 0
					min_st_cost[curr_i][curr_j] = min(new_coins, min_st_cost[curr_i][curr_j])
		final_value = min_st_cost[0][0] + 1
		return final_value


class Solution:

	def minPoints(self, points, M, N):
		mat = [[0 for i in range(N)] for j in range(M)]
		if points[-1][-1] >= 0:
			mat[-1][-1] = 1
		else:
			mat[-1][-1] = abs(points[-1][-1]) + 1
		for i in range(M - 2, -1, -1):
			x = mat[i + 1][N - 1] - points[i][N - 1]
			if x <= 0:
				mat[i][N - 1] = 1
			else:
				mat[i][N - 1] = x
		for i in range(N - 2, -1, -1):
			x = mat[M - 1][i + 1] - points[M - 1][i]
			if x <= 0:
				mat[M - 1][i] = 1
			else:
				mat[M - 1][i] = x
		for i in range(M - 2, -1, -1):
			for j in range(N - 2, -1, -1):
				x = min(mat[i + 1][j], mat[i][j + 1]) - points[i][j]
				if x <= 0:
					mat[i][j] = 1
				else:
					mat[i][j] = x
		return mat[0][0]


class Solution:

	def minPoints(self, arr, M, N):
		dp = [[78263476 for j in range(len(arr[0]))] for i in range(len(arr))]
		for i in range(len(arr) - 1, -1, -1):
			for j in range(len(arr[0]) - 1, -1, -1):
				if i == len(arr) - 1 and j == len(arr[0]) - 1:
					dp[i][j] = min(0, arr[i][j])
				else:
					(choice1, choice2) = (78263476, 78263476)
					if i + 1 < len(arr):
						choice1 = min(dp[i + 1][j] + arr[i][j], 0)
					if j + 1 < len(arr[0]):
						choice2 = min(dp[i][j + 1] + arr[i][j], 0)
					if abs(choice1) > abs(choice2):
						dp[i][j] = choice2
					else:
						dp[i][j] = choice1
		return abs(dp[0][0]) + 1


class Solution:

	def minPoints(self, points, M, N):
		(m, n) = (M, N)
		dp = [[-1 for i in range(n)] for j in range(m)]
		dp[m - 1][n - 1] = 1 if points[m - 1][n - 1] >= 0 else 1 - points[m - 1][n - 1]
		for j in range(n - 2, -1, -1):
			if points[m - 1][j] >= 0:
				dp[m - 1][j] = max(1, dp[m - 1][j + 1] - points[m - 1][j])
			else:
				dp[m - 1][j] = dp[m - 1][j + 1] - points[m - 1][j]
		for i in range(m - 2, -1, -1):
			if points[i][n - 1] >= 0:
				dp[i][n - 1] = max(1, dp[i + 1][n - 1] - points[i][n - 1])
			else:
				dp[i][n - 1] = dp[i + 1][n - 1] - points[i][n - 1]
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				if points[i][j] >= 0:
					dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - points[i][j], 1)
				else:
					dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - points[i][j]
		return dp[0][0]


class Solution:

	def minPoints(self, points, M, N):
		dp = [[float('inf')] * (N + 1) for i in range(M + 1)]
		dp[M][N - 1] = 1
		dp[M - 1][N] = 1
		for i in reversed(range(M)):
			for j in reversed(range(N)):
				dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - points[i][j], 1)
		return dp[0][0]