Given a NxN matrix of positive integers. There are only three possible moves from a cell Matrix[r][c].
	Matrix [r+1] [c]
	Matrix [r+1] [c-1]
	Matrix [r+1] [c+1]
Starting from any column in row 0 return the largest sum of any of the paths up to row N-1.
NOTE: We can start from any column in zeroth row and can end at any column in (N-1)th row.
Example 1:
Input: N = 2
Matrix = {{348, 391},
          {618, 193}}
Output: 1009
Explaination: The best path is 391 -> 618. 
It gives the sum = 1009.
Example 2:
Input: N = 2
Matrix = {{2, 2},
          {2, 2}}
Output: 4
Explaination: No matter which path is 
chosen, the output is 4.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maximumPath() which takes the size N and the Matrix as input parameters and returns the highest maximum path sum.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N*N)
Constraints:
1 ≤ N ≤ 500
1 ≤ Matrix[i][j] ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def maximumPath(self, N, Matrix):

        # code here

Solutions:
class Solution:

	def util(self, a, i, j, n, m):
		global dp
		if i >= n or i < 0 or j >= m or (j < 0):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = a[i][j] + max(self.util(a, i + 1, j, n, m), max(self.util(a, i + 1, j + 1, n, m), self.util(a, i + 1, j - 1, n, m)))
		return dp[i][j]

	def maximumPath(self, N, Matrix):
		ans = 0
		global dp
		dp = [[-1 for i in range(N)] for j in range(N)]
		for i in range(N):
			ans = max(ans, self.util(Matrix, 0, i, N, N))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):
		dp = []
		for i in range(N):
			temp = []
			for j in range(N):
				temp.append(0)
			dp.append(temp)
		for i in range(N):
			dp[0][i] = Matrix[0][i]
		for i in range(1, N):
			for j in range(N):
				if j == 0:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1]) + Matrix[i][j]
				elif j + 1 == N:
					dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + Matrix[i][j]
				else:
					dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + Matrix[i][j]
		return max(dp[-1])


class Solution:

	def maximumPath(self, n, a):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		for j in range(n):
			dp[0][j] = a[0][j]
		for i in range(1, n):
			for j in range(n):
				up = a[i][j] + dp[i - 1][j]
				ld = -1000000000.0
				if j - 1 >= 0:
					ld = a[i][j] + dp[i - 1][j - 1]
				rd = -1000000000.0
				if j + 1 < n:
					rd = a[i][j] + dp[i - 1][j + 1]
				dp[i][j] = max(up, ld, rd)
		return max([dp[n - 1][j] for j in range(n)])


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			dp[0][i] = Matrix[0][i]
		for i in range(1, N):
			for j in range(0, N):
				if j == 0:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1])
				elif j == N - 1:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1])
				else:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
		rst = 0
		for i in range(N):
			rst = max(rst, dp[N - 1][i])
		return rst


class Solution:

	def maximumPath(self, N, Matrix):
		for i in range(N - 2, -1, -1):
			for j in range(N):
				if 0 < j < N - 1:
					Matrix[i][j] += max(max(Matrix[i + 1][j - 1], Matrix[i + 1][j]), Matrix[i + 1][j + 1])
				elif j == 0:
					Matrix[i][j] += max(Matrix[i + 1][j + 1], Matrix[i + 1][j])
				elif j == N - 1:
					Matrix[i][j] += max(Matrix[i + 1][j - 1], Matrix[i + 1][j])
		return max(Matrix[0])


class Solution:

	def maximumPath(self, N, Matrix):

		def fun(i, j):
			if j < 0 or j >= len(matrix[0]):
				return 0
			if i == 0:
				return matrix[0][j]
			if dp[i][j] != -1:
				return dp[i][j]
			l1 = matrix[i][j] + fun(i - 1, j)
			l2 = matrix[i][j] + fun(i - 1, j - 1)
			l3 = matrix[i][j] + fun(i - 1, j + 1)
			dp[i][j] = max(l1, max(l2, l3))
			return dp[i][j]
		n = N
		matrix = Matrix
		maxi = 0
		dp = [[-1 for i in range(n)] for j in range(n)]
		for j in range(n - 1, -1, -1):
			re = fun(n - 1, j)
			maxi = max(maxi, re)
		return maxi


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[0 for _ in range(N)] for _ in range(N)]
		dp[0] = Matrix[0]
		for r in range(1, N):
			for c in range(N):
				temp = float('-inf')
				dir = [-1, 0, 1]
				for d in dir:
					if 0 <= c + d < N:
						temp = max(temp, dp[r - 1][c + d])
				dp[r][c] = Matrix[r][c] + temp
		return max(dp[N - 1])


class Solution:

	def maximumPath(self, N, Matrix):
		n = len(Matrix)
		m = len(Matrix[0])
		t = [[0 for x in range(m)] for y in range(n)]
		for j in range(m):
			t[0][j] = Matrix[0][j]
		for i in range(1, n):
			for j in range(0, m):
				above = Matrix[i][j] + t[i - 1][j]
				left = Matrix[i][j]
				if j - 1 >= 0:
					left += t[i - 1][j - 1]
				else:
					left += -1000000000.0
				right = Matrix[i][j]
				if j + 1 < m:
					right += t[i - 1][j + 1]
				else:
					right += -1000000000.0
				t[i][j] = max(above, max(left, right))
		mini = -100000
		for i in range(m):
			mini = max(mini, t[n - 1][i])
		return mini


class Solution:

	def maximumPath(self, n, mat):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		dp = [[0 for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(n):
				if i == 0:
					dp[i][j] = mat[i][j]
					continue
				up = mat[i][j] + dp[i - 1][j]
				ld = rd = -sys.maxsize
				if j > 0:
					ld = mat[i][j] + dp[i - 1][j - 1]
				if j < n - 1:
					rd = mat[i][j] + dp[i - 1][j + 1]
				dp[i][j] = max(dp[i][j], max(up, max(ld, rd)))
		return max(dp[n - 1])

	def solve(self, i, j, mat, dp, n):
		import sys
		if i < 0 or j < 0:
			return -sys.maxsize
		if i == 0:
			dp[i][j] = mat[i][j]
			return dp[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		up = mat[i][j] + self.solve(i - 1, j, mat, dp, n)
		ld = -sys.maxsize
		if j > 0:
			ld = mat[i][j] + self.solve(i - 1, j - 1, mat, dp, n)
		rd = -sys.maxsize
		if j < n - 1:
			rd = mat[i][j] + self.solve(i - 1, j + 1, mat, dp, n)
		dp[i][j] = max(up, max(ld, rd))
		return dp[i][j]


class Solution:

	def maximumPath(self, N, arr):
		for i in range(1, len(arr)):
			for j in range(len(arr[0])):
				if j == 0:
					arr[i][j] += max(arr[i - 1][j + 1], arr[i - 1][j])
				elif j == len(arr) - 1:
					arr[i][j] += max(arr[i - 1][j], arr[i - 1][j - 1])
				else:
					arr[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j], arr[i - 1][j + 1])
		return max(arr[-1])


import numpy as np

class Solution:

	def rec_sol(self, R, C, r, c, Matrix, dp):
		if r == 0:
			return 0
		if dp[r][c] != -1:
			return dp[r][c]
		temp = self.rec_sol(R, C, r - 1, c, Matrix, dp)
		if c > 1:
			temp = max(temp, self.rec_sol(R, C, r - 1, c - 1, Matrix, dp))
		if c < C:
			temp = max(temp, self.rec_sol(R, C, r - 1, c + 1, Matrix, dp))
		dp[r][c] = temp + Matrix[r - 1][c - 1]
		return dp[r][c]

	def dp_sol(self, R, C, Matrix):
		dp = np.array([[0] * (C + 1)] * (R + 1))
		for i in range(1, R + 1):
			for j in range(1, C + 1):
				temp = dp[i - 1][j]
				if j > 1:
					temp = max(temp, dp[i - 1][j - 1])
				if j < C:
					temp = max(temp, dp[i - 1][j + 1])
				dp[i][j] = temp + Matrix[i - 1][j - 1]
		return max(dp[R])

	def maximumPath(self, N, Matrix):
		R = len(Matrix)
		C = len(Matrix[0])
		return self.dp_sol(R, C, Matrix)


class Solution:

	def maximumPath(self, n, mat):
		import sys
		sys.setrecursionlimit(10 ** 9)
		dp = [[-sys.maxsize for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(n):
				if i == 0:
					dp[i][j] = mat[i][j]
					continue
				up = mat[i][j] + dp[i - 1][j]
				uld = urd = -sys.maxsize
				if j - 1 >= 0:
					uld = mat[i][j] + dp[i - 1][j - 1]
				if j + 1 < n:
					urd = mat[i][j] + dp[i - 1][j + 1]
				dp[i][j] = max(dp[i][j], max(up, max(urd, uld)))
		return max(dp[n - 1])

	def solve(self, i, j, n, mat, dp):
		import sys
		if i == n - 1:
			dp[i][j] = mat[i][j]
			return mat[i][j]
		if dp[i][j] != -sys.maxsize:
			return dp[i][j]
		ld = rd = -sys.maxsize
		down = mat[i][j] + self.solve(i + 1, j, n, mat, dp)
		if j - 1 >= 0:
			ld = mat[i][j] + self.solve(i + 1, j - 1, n, mat, dp)
		if j + 1 < n:
			rd = mat[i][j] + self.solve(i + 1, j + 1, n, mat, dp)
		max_ = max(down, max(ld, rd))
		dp[i][j] = max(dp[i][j], max_)
		return dp[i][j]


class Solution:

	def maximumPath(self, N, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		dp = [[-1] * m for _ in range(n)]

		def f(i, j):
			if j < 0 or j >= m:
				return -1000000000.0
			if i == 0:
				return matrix[0][j]
			if dp[i][j] != -1:
				return dp[i][j]
			s = matrix[i][j] + f(i - 1, j)
			l = matrix[i][j] + f(i - 1, j - 1)
			r = matrix[i][j] + f(i - 1, j + 1)
			dp[i][j] = max(max(s, l), r)
			return dp[i][j]
		ans = -1000000000.0
		for j in range(m):
			ans = max(ans, f(n - 1, j))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):
		arr = []
		for i in range(0, N):
			w = []
			for j in range(0, N):
				w.append(-1)
			arr.append(w)

		def wtf(Matrix, arr, col, v):
			if v == N - 1:
				return Matrix[v][col]
			if arr[v][col] != -1:
				return arr[v][col]
			x = 0
			z = 0
			if col > 0:
				x = Matrix[v][col] + wtf(Matrix, arr, col - 1, v + 1)
			y = wtf(Matrix, arr, col, v + 1) + Matrix[v][col]
			if col < N - 1:
				z = wtf(Matrix, arr, col + 1, v + 1) + Matrix[v][col]
			arr[v][col] = max(x, y, z)
			return arr[v][col]
		ans = []
		for i in range(0, N):
			s = wtf(Matrix, arr, i, 0)
			ans.append(s)
		return max(ans)


class Solution:

	def maximumPath(self, N, Matrix):

		def solve(row, col, dp):
			if col < 0 or col >= N:
				return -1
			if row == N - 1:
				return Matrix[row][col]
			if dp[row][col] != -1:
				return dp[row][col]
			dp[row][col] = Matrix[row][col] + max(solve(row + 1, col, dp), solve(row + 1, col - 1, dp), solve(row + 1, col + 1, dp))
			return dp[row][col]
		maxi = -1
		dp = [[-1 for i in range(N)] for j in range(N)]
		for col in range(N):
			pathsum = solve(0, col, dp)
			maxi = max(maxi, pathsum)
		return maxi


from math import inf

class Solution:

	def maximumPath(self, N, Matrix):
		n = N
		tabarray = [[0] * n for i in range(n)]
		tabarray[n - 1] = Matrix[n - 1]
		for i in range(n - 2, -1, -1):
			for j in range(n):
				if j == 0:
					tabarray[i][j] = Matrix[i][j] + max(tabarray[i + 1][j], tabarray[i + 1][j + 1])
				elif j == n - 1:
					tabarray[i][j] = Matrix[i][j] + max(tabarray[i + 1][j], tabarray[i + 1][j - 1])
				else:
					tabarray[i][j] = Matrix[i][j] + max(tabarray[i + 1][j], tabarray[i + 1][j + 1], tabarray[i + 1][j - 1])
		return max(tabarray[0])


class Solution:

	def maximumPath(self, n, matrix):
		if n == 1:
			return matrix[0][0]
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[0][i] = matrix[0][i]
		for i in range(1, n):
			for j in range(n):
				l = [[-1, 0], [-1, -1], [-1, 1]]
				for (a, b) in l:
					(nr, nc) = (i + a, b + j)
					if nr < n and nr >= 0 and (nc < n) and (nc >= 0):
						dp[i][j] = max(dp[i][j], dp[nr][nc] + matrix[i][j])
		return max(dp[n - 1])


class Solution:

	def maximumPath(self, n, mat):
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			temp = [0] * n
			for j in range(n - 1, -1, -1):
				if i == n - 1:
					temp[j] = mat[i][j]
					continue
				left = down = right = mat[i][j]
				if j > 0:
					left += dp[j - 1]
				else:
					left = -1000000000.0
				down += dp[j]
				if j < n - 1:
					right += dp[j + 1]
				else:
					right = -1000000000.0
				temp[j] = max(left, down, right)
			dp[:] = temp[:]
		maxi = -1000000000.0
		for i in range(n):
			maxi = max(maxi, dp[i])
		return maxi


class Solution:

	def maximumPath(self, n, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		dp = [[-1 for _ in range(m)] for _ in range(n)]

		def helper(i, j):
			if j < 0 or j >= m:
				return -1000000000.0
			if i == n - 1:
				return matrix[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			left = matrix[i][j] + helper(i + 1, j - 1)
			down = matrix[i][j] + helper(i + 1, j)
			right = matrix[i][j] + helper(i + 1, j + 1)
			dp[i][j] = max(left, down, right)
			return dp[i][j]
		maxi = -1000000000.0
		for i in range(m):
			maxi = max(maxi, helper(0, i))
		return maxi


class Solution:

	def maximumPath(self, N, Matrix):
		m = len(Matrix[0])
		dp = [[-1] * m for _ in range(N)]

		def f(i, j):
			if j < 0 or j >= m:
				return float('-inf')
			if i == 0:
				return Matrix[0][j]
			if dp[i][j] != -1:
				return dp[i][j]
			s = Matrix[i][j] + f(i - 1, j)
			l = Matrix[i][j] + f(i - 1, j - 1)
			r = Matrix[i][j] + f(i - 1, j + 1)
			dp[i][j] = max(max(s, l), r)
			return dp[i][j]
		ans = float('-inf')
		for j in range(m):
			ans = max(ans, f(N - 1, j))
		return ans


from collections import defaultdict

class Solution:

	def maximumPath(self, N, Matrix):
		d = dict()

		def dp(x, y):
			if (x, y) in d:
				return d[x, y]
			if y < 0 or y >= len(Matrix[0]) or x == len(Matrix):
				return 0
			r = max(dp(x + 1, y), dp(x + 1, y - 1), dp(x + 1, y + 1)) + Matrix[x][y]
			d[x, y] = r
			return r
		ans = 0
		for y in range(len(Matrix[0])):
			ans = max(ans, dp(0, y))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):
		dic = [[-1 for j in range(N)] for i in range(N)]
		ma = 0

		def solve(r, c, arr):
			if c < 0 or c >= N:
				return -1
			if r == N:
				return 0
			if dic[r][c] != -1:
				return dic[r][c]
			dic[r][c] = arr[r][c] + max(solve(r + 1, c - 1, arr), solve(r + 1, c, arr), solve(r + 1, c + 1, arr))
			return dic[r][c]
		for k in range(N):
			ma = max(ma, solve(0, k, Matrix))
		return ma


class Solution:

	def maximumPath(self, N, Matrix):
		dpTable = [[0 for _ in range(N)] for _ in range(N + 1)]
		for row in range(1, N + 1):
			for col in range(N):
				maxValue = dpTable[row - 1][col]
				if col > 0:
					maxValue = max(maxValue, dpTable[row - 1][col - 1])
				if col < N - 1:
					maxValue = max(maxValue, dpTable[row - 1][col + 1])
				dpTable[row][col] = maxValue + Matrix[row - 1][col]
		return max(dpTable[-1])


class Solution:

	def maximumPath(self, N, matrix):
		max_res = 0
		arr = [[-1 for i in range(len(matrix))] for j in range(len(matrix))]
		for i in range(len(matrix)):
			max_res = max(max_res, self.maxPathHelper(matrix, 0, i, arr))
		return max_res

	def maxPathHelper(self, matrix, row, col, arr):
		if row == len(matrix):
			return 0
		if col < 0 or col >= len(matrix):
			return 0
		if arr[row][col] != -1:
			return arr[row][col]
		res1 = matrix[row][col] + self.maxPathHelper(matrix, row + 1, col, arr)
		res2 = matrix[row][col] + self.maxPathHelper(matrix, row + 1, col - 1, arr)
		res3 = matrix[row][col] + self.maxPathHelper(matrix, row + 1, col + 1, arr)
		res = max(res1, res2, res3)
		arr[row][col] = res
		return res


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[-1 for i in range(N)] for j in range(N)]

		def maxPath(dp, r, c):
			if r < 0 or c < 0 or r >= N or (c >= N):
				return -99999
			if r == N - 1:
				return Matrix[r][c]
			if dp[r][c] != -1:
				return dp[r][c]
			else:
				option1 = maxPath(dp, r + 1, c)
				option2 = maxPath(dp, r + 1, c - 1)
				option3 = maxPath(dp, r + 1, c + 1)
				dp[r][c] = Matrix[r][c] + max([option1, option2, option3])
			return dp[r][c]
		maxi = -9999
		for i in range(0, N):
			maxi = max(maxi, maxPath(dp, 0, i))
		return maxi


import math

class Solution:

	def maximumPath(self, N, Matrix):
		t = [[-1] * N for _ in range(N)]

		def rec(r, c, N):
			if c < 0 or c >= N:
				return -1
			if t[r][c] != -1:
				return t[r][c]
			if N - r == 1:
				return Matrix[r][c]
			min_path = max(rec(r + 1, c, N), rec(r + 1, c - 1, N), rec(r + 1, c + 1, N))
			t[r][c] = min_path + Matrix[r][c]
			return t[r][c]
		min_path = -1
		for i in range(N):
			min_path = max(rec(0, i, N), min_path)
		return min_path


class Solution:

	def maximumPath(self, N, Matrix):
		if N == 1:
			return max(Matrix[0])
		ans = -1
		for i in range(1, N):
			for j in range(N):
				if j > 0 and j < N - 1:
					cur = max(Matrix[i - 1][j - 1], Matrix[i - 1][j + 1], Matrix[i - 1][j])
					Matrix[i][j] += cur
					ans = max(ans, Matrix[i][j])
				elif j > 0:
					cur = max(Matrix[i - 1][j - 1], Matrix[i - 1][j])
					Matrix[i][j] += cur
					ans = max(Matrix[i][j], ans)
				elif j < N - 1:
					cur = max(Matrix[i - 1][j + 1], Matrix[i - 1][j])
					Matrix[i][j] += cur
					ans = max(Matrix[i][j], ans)
		return ans


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[-1 for i in range(N)] for j in range(N)]

		def helper(i, j):
			if i >= N or j < 0 or j >= N:
				return float('-inf')
			if i == N - 1:
				return Matrix[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			dL = Matrix[i][j] + helper(i + 1, j - 1)
			d = Matrix[i][j] + helper(i + 1, j)
			dR = Matrix[i][j] + helper(i + 1, j + 1)
			dp[i][j] = max(dL, max(d, dR))
			return dp[i][j]
		ans = float('-inf')
		for j in range(N):
			ans = max(ans, helper(0, j))
		return ans


class Solution:

	def maximumPath(self, N, matrix):
		m = len(matrix)
		n = len(matrix[0])
		dp = [[0 for _ in range(n)] for _ in range(m)]
		dp[0] = matrix[0]
		for i in range(m):
			for j in range(n):
				if i + 1 < m:
					dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + matrix[i + 1][j])
				if i + 1 < m and j + 1 < n:
					dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + matrix[i + 1][j + 1])
				if i + 1 < m and j - 1 >= 0:
					dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + matrix[i + 1][j - 1])
		return max(dp[-1])


class Solution:

	def maximumPath(self, N, Matrix):
		for i in range(1, N):
			for j in range(0, N):
				if j == 0 or j == N - 1:
					if j == 0:
						Matrix[i][j] += max(Matrix[i - 1][j], Matrix[i - 1][j + 1])
					else:
						Matrix[i][j] += max(Matrix[i - 1][j], Matrix[i - 1][j - 1])
				else:
					Matrix[i][j] += max(Matrix[i - 1][j], Matrix[i - 1][j - 1], Matrix[i - 1][j + 1])
		return max(Matrix[N - 1])


class Solution:

	def maximumPath(self, n, grid):
		import sys
		dp = [[-sys.maxsize for j in range(n)] for i in range(n)]
		max_ = -sys.maxsize
		for i in range(n):
			for j in range(n):
				if i == 0:
					dp[i][j] = grid[i][j]
					continue
				ld = rd = -sys.maxsize
				up = grid[i][j] + dp[i - 1][j]
				if j > 0:
					ld = grid[i][j] + dp[i - 1][j - 1]
				if j < n - 1:
					rd = grid[i][j] + dp[i - 1][j + 1]
				dp[i][j] = max(dp[i][j], max(up, max(ld, rd)))
		for j in range(n):
			max_ = max(max_, dp[n - 1][j])
		return max_


class Solution:

	def maximumPath(self, N, Matrix):
		if N == 1:
			return Matrix[0][0]
		dyn = [[0 for _ in range(N)] for _ in range(N)]
		for j in range(N):
			dyn[0][j] = Matrix[0][j]
		for i in range(1, N):
			for j in range(N):
				if j == 0:
					dyn[i][j] = Matrix[i][j] + max([dyn[i - 1][j], dyn[i - 1][j + 1]])
				elif j == N - 1:
					dyn[i][j] = Matrix[i][j] + max([dyn[i - 1][j], dyn[i - 1][j - 1]])
				else:
					dyn[i][j] = Matrix[i][j] + max([dyn[i - 1][j], dyn[i - 1][j - 1], dyn[i - 1][j + 1]])
		max_sum = 0
		for j in range(N):
			if dyn[N - 1][j] > max_sum:
				max_sum = dyn[N - 1][j]
		return max_sum


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[-1] * N for i in range(N)]

		def uniq(i, j):
			if j < 0 or j > N - 1:
				return 0
			elif i == 0:
				return Matrix[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = Matrix[i][j] + max(uniq(i - 1, j), uniq(i - 1, j - 1), uniq(i - 1, j + 1))
			return dp[i][j]
		maxi = 0
		for col in range(N):
			maxi = max(maxi, uniq(N - 1, col))
		return maxi


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[0 for i in range(N + 2)] for i in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + Matrix[i - 1][j - 1]
		m = -1000000000.0
		for i in range(1, N + 1):
			m = max(dp[N][i], m)
		return m


class Solution:

	def solve(self, r, c, arr, N, dp):
		if r >= N:
			return 0
		if dp[r][c] != -1:
			return dp[r][c]
		MIN = arr[r][c] + self.solve(r + 1, c, arr, N, dp)
		if c - 1 >= 0:
			MIN = max(MIN, arr[r][c - 1] + self.solve(r + 1, c - 1, arr, N, dp))
		if c + 1 < N:
			MIN = max(MIN, arr[r][c + 1] + self.solve(r + 1, c + 1, arr, N, dp))
		dp[r][c] = MIN
		return MIN

	def maximumPath(self, N, Matrix):
		ans = 0
		dp = [[-1 for _ in i] for i in Matrix]
		for i in range(N):
			ans = max(ans, self.solve(0, i, Matrix, N, dp))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):

		def max_path(matrix, i, j, n, dp):
			if i >= n or j >= n or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			else:
				t1 = max_path(matrix, i + 1, j - 1, n, dp)
				t2 = max_path(matrix, i + 1, j, n, dp)
				t3 = max_path(matrix, i + 1, j + 1, n, dp)
				dp[i][j] = matrix[i][j] + max(t1, t2, t3)
				return dp[i][j]
		m = float('-inf')
		dp = [[-1 for j in range(N)] for i in range(N)]
		for j in range(N):
			temp = max_path(Matrix, 0, j, N, dp)
		for j in range(N):
			m = max(m, dp[0][j])
		return m


class Solution:

	def maximumPath(self, N, Matrix):
		adj = [-1, 0, 1]
		for row in range(1, N):
			for col in range(N):
				maximum = Matrix[row][col]
				for path in adj:
					if col + path >= 0 and col + path < N:
						maximum = max(Matrix[row - 1][col + path] + Matrix[row][col], maximum)
				Matrix[row][col] = maximum
		res = 0
		for pos in range(N):
			res = max(res, Matrix[N - 1][pos])
		return res


def solve(arr, i, j):
	if j < 0 or j > len(arr) - 1:
		return 0
	elif i == len(arr) - 1:
		return arr[i][j]
	elif f[i][j] != -1:
		return f[i][j]
	path1 = solve(arr, i + 1, j - 1)
	path2 = solve(arr, i + 1, j)
	path3 = solve(arr, i + 1, j + 1)
	f[i][j] = arr[i][j] + max(path1, path2, path3)
	return f[i][j]

class Solution:

	def maximumPath(self, N, Matrix):
		global f
		f = [[-1 for i in range(N)] for j in range(N)]
		ans = 0
		for j in range(N):
			ans = max(ans, solve(Matrix, 0, j))
		return ans


class Solution:
	dp = []

	def gen(self, n, matrix, x, y):
		if x > n or y > n or y < 0:
			return 0
		if x == n:
			return matrix[x][y]
		p = 0
		q = 0
		r = 0
		if self.dp[x][y] != -1:
			return self.dp[x][y]
		if x + 1 <= n:
			p = self.gen(n, matrix, x + 1, y) + matrix[x][y]
		if x + 1 <= n and y - 1 >= 0:
			q = self.gen(n, matrix, x + 1, y - 1) + matrix[x][y]
		if x + 1 <= n and y + 1 <= n:
			r = self.gen(n, matrix, x + 1, y + 1) + matrix[x][y]
		self.dp[x][y] = max(p, q, r)
		return max(p, q, r)

	def maximumPath(self, N, Matrix):
		dp = []
		for i in range(N):
			arr = []
			for j in range(N):
				arr.append(-1)
			dp.append(arr)
		for i in range(N):
			dp[N - 1][i] = Matrix[N - 1][i]
		for i in range(N - 2, -1, -1):
			for j in range(N):
				if j == 0:
					dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + Matrix[i][j]
				elif j == N - 1:
					dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - 1]) + Matrix[i][j]
				else:
					dp[i][j] = max(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + Matrix[i][j]
		return max(dp[0])


import sys

class Solution:

	def maximumPath(self, N, Matrix):

		def path(i, j, N, Matrix, dp):
			if j < 0 or j >= N:
				return -sys.maxsize
			if i == 0:
				return Matrix[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			s = Matrix[i][j] + path(i - 1, j, N, Matrix, dp)
			l = Matrix[i][j] + path(i - 1, j - 1, N, Matrix, dp)
			r = Matrix[i][j] + path(i - 1, j + 1, N, Matrix, dp)
			dp[i][j] = max(s, l, r)
			return dp[i][j]
		dp = [[-1 for i in range(N)] for j in range(N)]
		s = -sys.maxsize
		for i in range(N):
			m = path(N - 1, i, N, Matrix, dp)
			s = max(s, m)
		return s


class Solution:

	def maximumPath(self, n, mat):
		n = len(mat)
		dp = [[-1] * n for i in range(n)]

		def findmaxpath(i, j, n):
			if i < 0 or j < 0 or i >= n or (j >= n):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			val = 0
			val = findmaxpath(i + 1, j, n)
			val = max(val, findmaxpath(i + 1, j - 1, n))
			val = max(val, findmaxpath(i + 1, j + 1, n))
			dp[i][j] = val + mat[i][j]
			return dp[i][j]
		maxval = 0
		for i in range(n):
			maxval = max(maxval, findmaxpath(0, i, n))
		return maxval


class Solution:

	def maximumPath(self, N, Matrix):
		mv = [-1, 0, 1]
		for r in range(1, N):
			for c in range(N):
				total = 0
				for j in mv:
					y = c + j
					if 0 <= y < N:
						total = max(total, Matrix[r - 1][y])
				Matrix[r][c] += total
		ans = max(Matrix[-1])
		return ans


class Solution:

	def maximumPath(self, n, matrix):
		dp = [[0 for i in range(n)] for _ in range(n)]
		for i in range(n):
			dp[0][i] = matrix[0][i]
		for i in range(1, n):
			for j in range(n):
				up = 0
				left = 0
				right = 0
				if i - 1 >= 0:
					up = dp[i - 1][j]
				if i - 1 >= 0 and j - 1 >= 0:
					left = dp[i - 1][j - 1]
				if i - 1 >= 0 and j + 1 < n:
					right = dp[i - 1][j + 1]
				dp[i][j] = matrix[i][j] + max(up, left, right)
		return max(dp[n - 1])


class Solution:

	def solve(self, r, c, matrix, box):
		if c < 0 or c >= len(matrix):
			return -1
		if r == len(matrix) - 1:
			return matrix[r][c]
		if box[r][c] != -1:
			return box[r][c]
		box[r][c] = matrix[r][c] + max(self.solve(r + 1, c, matrix, box), self.solve(r + 1, c + 1, matrix, box), self.solve(r + 1, c - 1, matrix, box))
		return box[r][c]

	def maximumPath(self, N, Matrix):
		box = [[-1 for _ in range(N)] for _ in range(N)]
		ans = 0
		for c in range(N):
			ans = max(ans, self.solve(0, c, Matrix, box))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):
		new_matrix = [Matrix[0]]
		for i in range(1, N):
			row = [0] * N
			for j in range(N):
				if j == 0:
					row[j] = Matrix[i][j] + max(new_matrix[-1][j], new_matrix[-1][j + 1])
				elif j == N - 1:
					row[j] = Matrix[i][j] + max(new_matrix[-1][j], new_matrix[-1][j - 1])
				else:
					row[j] = Matrix[i][j] + max(new_matrix[-1][j], new_matrix[-1][j + 1], new_matrix[-1][j - 1])
			new_matrix.append(row)
		return max(new_matrix[-1])


class Solution:

	def maximumPath(self, N, Matrix):
		aux = [[Matrix[i][j] for j in range(N)] for i in range(N)]

		def isValid(i, j):
			return 0 <= i and i < N and (0 <= j) and (j < N)
		for i in range(N):
			for j in range(N):
				if isValid(i + 1, j):
					aux[i + 1][j] = max(aux[i + 1][j], Matrix[i + 1][j] + aux[i][j])
				if isValid(i + 1, j - 1):
					aux[i + 1][j - 1] = max(aux[i + 1][j - 1], Matrix[i + 1][j - 1] + aux[i][j])
				if isValid(i + 1, j + 1):
					aux[i + 1][j + 1] = max(aux[i + 1][j + 1], Matrix[i + 1][j + 1] + aux[i][j])
		maxpath = 0
		for i in range(N):
			maxpath = max(maxpath, aux[N - 1][i])
		return maxpath


class Solution:

	def maximumPath(self, N, Matrix):
		dplast = [0 for i in range(N)]
		for i in range(N - 1, -1, -1):
			newdp = []
			for j in range(N):
				best = dplast[j]
				if j > 0:
					best = max(best, dplast[j - 1])
				if j < N - 1:
					best = max(best, dplast[j + 1])
				newdp.append(best + Matrix[i][j])
			dplast = newdp
		return max(dplast)


class Solution:

	def maximumPath(self, n, matrix):
		dp = [[-1 for i in range(n)] for j in range(n)]

		def solve(i, j, matrix):
			if j < 0 or j >= n:
				return -9999999
			if i == 0:
				return matrix[0][j]
			if dp[i][j] != -1:
				return dp[i][j]
			up = matrix[i][j] + solve(i - 1, j, matrix)
			left = matrix[i][j] + solve(i - 1, j - 1, matrix)
			right = matrix[i][j] + solve(i - 1, j + 1, matrix)
			dp[i][j] = max(up, left, right)
			return dp[i][j]
		ans = -99999999
		for j in range(n):
			temp = solve(n - 1, j, matrix)
			ans = max(ans, temp)
		return ans


class Solution:

	def solve(self, Matrix, x, y, cord, dp):
		if 0 <= x <= len(Matrix) - 1 and 0 <= y <= len(Matrix[0]) - 1:
			if dp[x][y] != None:
				return dp[x][y]
			else:
				a = self.solve(Matrix, x + 1, y, cord, dp)
				b = self.solve(Matrix, x + 1, y - 1, cord, dp)
				c = self.solve(Matrix, x + 1, y + 1, cord, dp)
				dp[x][y] = Matrix[x][y] + max(a, b, c)
				return dp[x][y]
		else:
			return 0

	def maximumPath(self, N, Matrix):
		start = Matrix[0]
		cord = [[1, 0], [1, -1], [1, 1]]
		(col, row) = (len(Matrix[0]), len(Matrix))
		dp = [[None for i in range(col + 1)] for j in range(row + 1)]
		res = []
		for i in range(len(start)):
			a = self.solve(Matrix, 0, i, cord, dp)
			res.append(a)
		return max(res)


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[-1 for i in range(N)] for i in range(N)]

		def do(i, j):
			if i < 0 or j < 0 or i >= N or (j >= N):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = Matrix[i][j] + max(do(i + 1, j - 1), do(i + 1, j), do(i + 1, j + 1))
			return dp[i][j]
		out = float('-inf')
		for i in range(N):
			out = max(out, do(0, i))
		return out


class Solution:

	def solve(self, i, j, n, mat, dp):
		if i >= n:
			return 0
		if j >= n or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		down = mat[i][j] + self.solve(i + 1, j, n, mat, dp)
		ldown = mat[i][j] + self.solve(i + 1, j - 1, n, mat, dp)
		rdown = mat[i][j] + self.solve(i + 1, j + 1, n, mat, dp)
		dp[i][j] = max(down, max(ldown, rdown))
		return dp[i][j]

	def maximumPath(self, N, Matrix):
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		i = 0
		j = 0
		maxi = 0
		for k in range(N):
			ans = self.solve(i, k, N, Matrix, dp)
			maxi = max(maxi, ans)
		return maxi


class Solution:

	def maximumPath(self, N, mat):

		def calc(r, c, dp):
			if dp[r][c] != -1:
				return dp[r][c]
			if r == 0:
				return mat[r][c]
			(l1, l2, l3) = (float('-inf'), float('-inf'), float('-inf'))
			if r - 1 >= 0 and c - 1 >= 0:
				l1 = mat[r][c] + calc(r - 1, c - 1, dp)
			if r - 1 >= 0:
				l2 = mat[r][c] + calc(r - 1, c, dp)
			if c + 1 < len(mat[0]):
				l3 = mat[r][c] + calc(r - 1, c + 1, dp)
			dp[r][c] = max(l1, l2, l3)
			return dp[r][c]
		dp = [[-1 for i in range(N)] for j in range(N)]
		ma = float('-inf')
		for i in range(N):
			ma = max(ma, calc(N - 1, i, dp))
		return ma


class Solution:

	def maximumPath(self, n, matrix):
		dp = [[0 for j in range(n)] for i in range(n)]
		for j in range(n):
			dp[0][j] = matrix[0][j]
		for i in range(1, n):
			for j in range(n):
				if j == 0:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]
				elif j == n - 1:
					dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j]
				else:
					dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]
		max_sum = dp[n - 1][0]
		for j in range(1, n):
			max_sum = max(max_sum, dp[n - 1][j])
		return max_sum


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[-1 for i in range(N)] for j in range(N)]
		maxi = 0
		for j in range(N):
			dp[0][j] = Matrix[0][j]
		for i in range(1, N):
			for j in range(N):
				ld = Matrix[i][j]
				if j - 1 < 0:
					ld = ld + float('-inf')
				else:
					ld = ld + dp[i - 1][j - 1]
				up = Matrix[i][j] + dp[i - 1][j]
				rd = Matrix[i][j]
				if j + 1 >= N:
					rd = rd + float('-inf')
				else:
					rd = rd + dp[i - 1][j + 1]
				dp[i][j] = max(ld, up, rd)
		for j in range(N):
			maxi = max(maxi, dp[N - 1][j])
		return maxi


class Solution:

	def fun(self, i, j, m, arr, dp):
		if j < 0 or j >= m:
			return float('-inf')
		if i == 0:
			return arr[0][j]
		if dp[i][j] != -1:
			return dp[i][j]
		up = arr[i][j] + self.fun(i - 1, j, m, arr, dp)
		ld = arr[i][j] + self.fun(i - 1, j - 1, m, arr, dp)
		rd = arr[i][j] + self.fun(i - 1, j + 1, m, arr, dp)
		dp[i][j] = max(up, ld, rd)
		return dp[i][j]

	def maximumPath(self, n, arr):
		(n, m) = (len(arr), len(arr[0]))
		dp = [[-1 for i in range(m)] for j in range(n)]
		for j in range(m):
			dp[0][j] = arr[0][j]
		for i in range(1, n):
			for j in range(m):
				(ld, rd) = (float('-inf'), float('-inf'))
				up = arr[i][j] + dp[i - 1][j]
				if j - 1 >= 0:
					ld = arr[i][j] + dp[i - 1][j - 1]
				if j + 1 < m:
					rd = arr[i][j] + dp[i - 1][j + 1]
				dp[i][j] = max(up, ld, rd)
		maxi = dp[n - 1][0]
		for j in range(m):
			maxi = max(maxi, dp[n - 1][j])
		return maxi


class Solution:

	def maximumPath(self, N, arr):
		dp = [[0] * len(arr[0]) for x in range(len(arr))]
		for i in range(len(arr[0])):
			dp[-1][i] = arr[-1][i]
		for i in range(len(arr) - 2, -1, -1):
			for j in range(len(arr[0])):
				(x, y, z) = (0, 0, 0)
				x = arr[i][j] + dp[i + 1][j]
				if j + 1 < len(arr[0]):
					y = arr[i][j] + dp[i + 1][j + 1]
				if j - 1 >= 0:
					z = arr[i][j] + dp[i + 1][j - 1]
				dp[i][j] = max(x, y, z)
		return max(dp[0])


class Solution:

	def maximumPath(self, N, Matrix):
		m = len(Matrix)
		n = len(Matrix[0])
		dp = [[0 for i in range(n)] for i in range(m)]
		for row in range(m - 1, -1, -1):
			for col in range(n - 1, -1, -1):
				if row == m - 1:
					right = 0
				else:
					right = dp[row + 1][col]
				if row == m - 1 or col == 0:
					rightback = 0
				else:
					rightback = dp[row + 1][col - 1]
				if row == m - 1 or col == n - 1:
					rightfront = 0
				else:
					rightfront = dp[row + 1][col + 1]
				dp[row][col] = Matrix[row][col] + max(right, rightback, rightfront)
		mx = 0
		for i in range(m):
			if dp[0][i] > mx:
				mx = dp[0][i]
		return mx


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[0 for i in range(N)] for i in range(N)]
		for i in range(N):
			dp[0][i] = Matrix[0][i]
		for i in range(1, N):
			for j in range(N):
				if j == 0 and j + 1 < N:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1])
				elif j - 1 >= 0 and j == N - 1:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1])
				elif j > 0 and j + 1 < N:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], max(dp[i - 1][j - 1], dp[i - 1][j + 1]))
				else:
					dp[i][j] = Matrix[i][j] + dp[i - 1][j]
		maxi = 0
		for i in range(N):
			maxi = max(maxi, dp[N - 1][i])
		return maxi


class Solution:

	def maximumPath(self, N, Matrix):
		if N == 1:
			return Matrix[0][0]
		t = [[0 for i in range(N + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if j < N:
					t[i][j] = max(t[i - 1][j - 1], t[i - 1][j], t[i - 1][j + 1]) + Matrix[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j - 1], t[i - 1][j]) + Matrix[i - 1][j - 1]
		gmax = 0
		for i in range(N + 1):
			gmax = max(gmax, t[N][i])
		return gmax


class Solution:

	def maximumPath(self, n, arr):
		if n == 1:
			return arr[0][0]
		for r in range(n - 2, -1, -1):
			for c in range(n - 1, -1, -1):
				temp = arr[r][c]
				arr[r][c] += arr[r + 1][c]
				if c + 1 < n:
					arr[r][c] = max(arr[r][c], temp + arr[r + 1][c + 1])
				if c - 1 >= 0:
					arr[r][c] = max(arr[r][c], temp + arr[r + 1][c - 1])
		return max(arr[0])


class Solution:

	def func(self, row, col, grid, dp):
		m = len(grid[0])
		if row == 0 and col >= 0 and (col < m):
			return grid[0][col]
		if col < 0 or col >= m or row < 0:
			return -int(1000000000.0)
		if dp[row][col] != -1:
			return dp[row][col]
		up = grid[row][col] + self.func(row - 1, col, grid, dp)
		leftDiag = grid[row][col] + self.func(row - 1, col - 1, grid, dp)
		rightDiag = grid[row][col] + self.func(row - 1, col + 1, grid, dp)
		dp[row][col] = max(max(up, leftDiag), rightDiag)
		return dp[row][col]

	def maximumPath(self, N, grid):
		maxi = -int(1000000000.0)
		dp = [[-1 for j in range(N)] for i in range(N)]
		for j in range(N):
			m = self.func(N - 1, j, grid, dp)
			maxi = max(maxi, m)
		return maxi


class Solution:

	def maximumPath(self, N, Matrix):

		def helper(i, j):
			if i == N:
				return 0
			if i >= N or j < 0 or j >= N:
				return float('-inf')
			if dp[i + 1][j] == -1:
				ans1 = helper(i + 1, j)
				dp[i + 1][j] = ans1
			else:
				ans1 = dp[i + 1][j]
			if dp[i + 1][j + 1] == -1:
				ans2 = helper(i + 1, j + 1)
				dp[i + 1][j + 1] = ans2
			else:
				ans2 = dp[i + 1][j + 1]
			if dp[i + 1][j - 1] == -1:
				ans3 = helper(i + 1, j - 1)
				dp[i + 1][j - 1] = ans3
			else:
				ans3 = dp[i + 1][j - 1]
			return Matrix[i][j] + max(ans1, ans2, ans3)
		ans = 0
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		for i in range(N):
			ans = max(ans, helper(0, i))
		return ans


import sys

class Solution:

	def maximumPath(self, n, Matrix):
		dp = [[-1 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[0][i] = Matrix[0][i]
		for i in range(1, n):
			for j in range(n):
				dp[i][j] = dp[i - 1][j]
				if j - 1 >= 0:
					dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])
				if j + 1 < n:
					dp[i][j] = max(dp[i][j], dp[i - 1][j + 1])
				dp[i][j] += Matrix[i][j]
		maxi = -sys.maxsize
		for i in range(n):
			maxi = max(dp[n - 1][i], maxi)
		return maxi


class Solution:

	def maximumPath(self, N, grid):
		n = len(grid)
		m = len(grid[0])
		dp = [[-1 for j in range(m)] for i in range(n)]
		maxi = float('-inf')
		for j in range(m):
			maxi = max(maxi, self.solve(n - 1, j, m, grid, dp))
		return maxi

	def solve(self, i, j, m, grid, dp):
		if j < 0 or j >= m:
			return float('-inf')
		if i == 0:
			return grid[0][j]
		if dp[i][j] != -1:
			return dp[i][j]
		path = max(self.solve(i - 1, j, m, grid, dp), self.solve(i - 1, j - 1, m, grid, dp), self.solve(i - 1, j + 1, m, grid, dp)) + grid[i][j]
		dp[i][j] = path
		return dp[i][j]


class Solution:

	def maximumPath(self, N, Matrix):

		def Solve(dp, i, j):
			if i < 0 or j < 0 or j >= N:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == 0:
				return Matrix[0][j]
			dp[i][j] = max(Solve(dp, i - 1, j - 1), Solve(dp, i - 1, j), Solve(dp, i - 1, j + 1)) + Matrix[i][j]
			return dp[i][j]
		ans = 0
		dp = []
		for i in range(N):
			dp.append([-1] * N)
		for i in range(N):
			for j in range(N):
				if i == 0:
					dp[i][j] = Matrix[i][j]
				else:
					left = dp[i - 1][max(j - 1, 0)]
					right = dp[i - 1][min(N - 1, j + 1)]
					same = dp[i - 1][j]
					dp[i][j] = max(left, right, same) + Matrix[i][j]
				if i == N - 1:
					ans = max(ans, dp[i][j])
		return ans


class Solution:

	def maximumPath(self, N, Matrix):

		def Solve(dp, i, j):
			if i < 0 or j < 0 or j >= N:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == 0:
				return Matrix[0][j]
			dp[i][j] = max(Solve(dp, i - 1, j - 1), Solve(dp, i - 1, j), Solve(dp, i - 1, j + 1)) + Matrix[i][j]
			return dp[i][j]
		ans = 0
		dp = []
		for i in range(N):
			dp.append([-1] * N)
		for i in range(N):
			ans = max(ans, Solve(dp, N - 1, i))
		return ans


class Solution:

	def maximumPath(self, N, Matrix):

		def manu(Matrix, dp):
			for i in range(N):
				dp[N - 1][i] = Matrix[N - 1][i]
			for i in range(N - 2, -1, -1):
				for j in range(N):
					x = Matrix[i][j] + dp[i + 1][j]
					if j - 1 >= 0:
						y = Matrix[i][j] + dp[i + 1][j - 1]
					else:
						y = -10 ** 9
					if j + 1 < N:
						z = Matrix[i][j] + dp[i + 1][j + 1]
					else:
						z = -10 ** 9
					dp[i][j] = max(x, max(y, z))
		maxi = -10 ** 9
		dp = [[-1 for i in range(N)] for i in range(N)]
		manu(Matrix, dp)
		for i in range(N):
			maxi = max(maxi, dp[0][i])
		return maxi


class Solution:

	def maximumPath(self, N, matrix):
		maxx = 0
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for row in range(N):
			for col in range(N):
				if row == 0:
					dp[row][col] = matrix[row][col]
				else:
					down = matrix[row][col] + dp[row - 1][col]
					if col < N - 1:
						downLeft = matrix[row][col] + dp[row - 1][col + 1]
					else:
						downLeft = 0
					if col > 0:
						downRight = matrix[row][col] + dp[row - 1][col - 1]
					else:
						downRight = 0
					dp[row][col] = max(down, downLeft, downRight)
		for idx in range(N):
			maxx = max(dp[-1][idx], maxx)
		return maxx

def findMax(matrix, dp, row, col):
	if col < 0 or col >= len(matrix[0]):
		return 0
	if row == len(matrix) - 1:
		return matrix[row][col]
	if (row, col) in dp:
		return dp[row, col]
	down = matrix[row][col] + findMax(matrix, dp, row + 1, col)
	downLeft = matrix[row][col] + findMax(matrix, dp, row + 1, col - 1)
	downRight = matrix[row][col] + findMax(matrix, dp, row + 1, col + 1)
	dp[row, col] = max(down, downLeft, downRight)
	return dp[row, col]


class Solution:

	def maximumPath(self, N, Matrix):
		dp = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			dp[N - 1][i] = Matrix[N - 1][i]
		for i in range(N - 2, -1, -1):
			for j in range(N):
				nxtSteps = [dp[i + 1][j]]
				if j < N - 1:
					nxtSteps.append(dp[i + 1][j + 1])
				if j > 0:
					nxtSteps.append(dp[i + 1][j - 1])
				dp[i][j] = max(nxtSteps) + Matrix[i][j]
		return max(dp[0])


class Solution:

	def maximumPath(self, n, a):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			for j in range(n):
				if i == 0:
					l = r = d = 0
				elif j == 0 and j < n - 1:
					d = dp[i - 1][j]
					r = dp[i - 1][j + 1]
					l = 0
				elif j == n - 1 and j > 0:
					d = dp[i - 1][j]
					l = dp[i - 1][j - 1]
					r = 0
				else:
					d = dp[i - 1][j]
					r = dp[i - 1][j + 1]
					l = dp[i - 1][j - 1]
				dp[i][j] = a[i][j] + max(l, r, d)
		return max(dp[-1])


class Solution:

	def maximumPath(self, N, Matrix):
		row = len(Matrix)
		col = len(Matrix[0])
		dp = [[-1 for i in range(col)] for j in range(row)]
		result = -1
		for i in range(row):
			for j in range(col):
				if i == 0:
					dp[i][j] = Matrix[i][j]
				elif j - 1 < 0:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1])
				elif j + 1 >= col:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1])
				else:
					dp[i][j] = Matrix[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1], dp[i - 1][j - 1])
		for i in range(col):
			result = max(result, dp[row - 1][i])
		return result


class Solution:

	def dfs(self, i, j, N, Matrix, dp):
		if i < 0 or i >= N or j < 0 or (j >= N):
			return -1000000000.0
		if i == N - 1:
			return Matrix[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		bottom = Matrix[i][j] + self.dfs(i + 1, j, N, Matrix, dp)
		bottomLeft = Matrix[i][j] + self.dfs(i + 1, j - 1, N, Matrix, dp)
		bottomRight = Matrix[i][j] + self.dfs(i + 1, j + 1, N, Matrix, dp)
		dp[i][j] = max(bottom, bottomLeft, bottomRight)
		return dp[i][j]

	def maximumPath(self, N, Matrix):
		maxSum = -1000000000.0
		dp = [[-1] * N for _ in range(N)]
		for j in range(N):
			maxSum = max(maxSum, self.dfs(0, j, N, Matrix, dp))
		return maxSum


class Solution:

	def maximumPath(self, N, Matrix):
		a = [[0 for hm in range(N + 1)] for hm in range(N + 1)]
		for hm in range(N - 1, -1, -1):
			for gm in range(N - 1, -1, -1):
				a[hm][gm] = Matrix[hm][gm] + max(a[hm + 1][gm], a[hm + 1][gm - 1], a[hm + 1][gm + 1])
		return max(a[0])