Given two integers N, M and a 2D matrix Mat of dimensions NxM, the task is to find the maximum sum of
an hourglass.
An hourglass is made of 7 cells in the following form.
    A B C
      D
    E F G
Example 1:
Input:
N=3,M=3
Mat=[[1,2,3],[4,5,6],[7,8,9]]
Output:
35
Explanation:
There is only one hour glass which is
1 2 3
   5
7 8 9 and its sum is 35.
Example 2:
Input:
N=2,M=3
Mat=[[1,2,3],[4,5,6]]
Output:
-1
Explanation:
There are no hour glasses in this matrix.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMaxSum() which takes the two integers N, M, and the 2D matrix Mat as input parameters and returns the maximum sum of an hourglass in the matrix. If there are no hourglasses, it returns -1.
Expected Time Complexity:O(N*M)
Expected Auxillary Space:O(1)
Constraints:
1<=N,M,Mat[i][j]<=1000

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def findMaxSum(self,N,M,Mat):

        #code here

Solutions:
class Solution:

	def findMaxSum(self, N, M, Mat):
		max_sum = -50000
		if N < 3 or M < 3:
			return -1
			exit()
		for i in range(0, N - 2):
			for j in range(0, M - 2):
				SUM = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
				if SUM > max_sum:
					max_sum = SUM
				else:
					continue
		return max_sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		maxsum = -1
		for i in range(N - 2):
			for j in range(M - 2):
				s = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
				maxsum = max(s, maxsum)
		return maxsum


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		max_sum = 0
		summ = 0
		for i in range(N - 2):
			for j in range(M - 2):
				summ = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				max_sum = max(max_sum, summ)
		return max_sum


class Solution:

	def findMaxSum(self, R, C, arr):
		if R < 3 or C < 3:
			return -1
		m = 0
		for i in range(0, R - 2):
			for j in range(0, C - 2):
				SUM = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1] + (arr[i + 2][j] + arr[i + 2][j + 1] + arr[i + 2][j + 2])
				m = max(m, SUM)
		return m


class Solution:

	def findMaxSum(self, rows, cols, grid):
		if N < 3 or M < 3:
			return -1
		gridsum = lambda r, c: sum(grid[r - 1][c - 1:c + 2]) + grid[r][c] + sum(grid[r + 1][c - 1:c + 2])
		return max((gridsum(r, c) for r in range(1, rows - 1) for c in range(1, cols - 1)))


class Solution:

	def hourglass_generator_sum(self, n, m, arr):
		row = n
		col = m
		return arr[n][m] + arr[n][m + 1] + arr[n][m + 2] + arr[n + 1][m + 1] + arr[n + 2][m] + arr[n + 2][m + 1] + arr[n + 2][m + 2]

	def findMaxSum(self, N, M, Mat):
		if N >= 3 and M >= 3:
			sum_arr = []
			for i in range(0, N - 2):
				for j in range(0, M - 2):
					sum_arr.append(self.hourglass_generator_sum(i, j, Mat))
			return max(sum_arr)
		else:
			return -1


class Solution:

	def findMaxSum(self, N, M, Mat):
		maxi = -1
		for i in range(N - 2):
			for j in range(M - 2):
				summa = 0
				summa += sum(Mat[i][j:j + 3])
				summa += Mat[i + 1][j + 1]
				summa += sum(Mat[i + 2][j:j + 3])
				maxi = max(maxi, summa)
		return maxi


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N >= 3 and M >= 3:
			max_sum = 0
			for i in range(N - 2):
				for j in range(M - 2):
					sum1 = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
					max_sum = max(max_sum, sum1)
			return max_sum
		else:
			return -1


class Solution:

	def findMaxSum(self, N, M, Mat):
		mx = 0
		if N < 3 or M < 3:
			return -1
		else:
			for i in range(N - 2):
				for j in range(M - 2):
					c = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
					if mx < c:
						mx = c
		return mx


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		maxi = 0
		sums = 0
		for i in range(N - 2):
			for j in range(M - 2):
				sums = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
				if sums > maxi:
					maxi = sums
				else:
					continue
		return maxi


class Solution:

	def findMaxSum(self, R, C, arr):
		max_sum = -1
		if R < 3 or C < 3:
			return -1
		for i in range(0, R - 2):
			for j in range(0, C - 2):
				SUM = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1] + (arr[i + 2][j] + arr[i + 2][j + 1] + arr[i + 2][j + 2])
				if SUM > max_sum:
					max_sum = SUM
				else:
					continue
		return max_sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		maxSum = 0
		if N < 3 or M < 3:
			return -1
		else:
			for i in range(0, N - 2):
				for j in range(0, M - 2):
					sum = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 2][j + 2] + Mat[i + 2][j + 1] + Mat[i + 2][j] + Mat[i + 1][j + 1]
					if maxSum < sum:
						maxSum = sum
			return maxSum


class Solution:

	def fun(self, mtr):
		return s

	def findMaxSum(self, n, m, Mat):
		if m < 3 or n < 3:
			return -1
		ma = 0
		for i in range(n - 2):
			for j in range(m - 2):
				s = 0
				s = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2]
				s += Mat[i + 1][j + 1]
				s += Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				if ma < s:
					ma = s
		return ma


class Solution:

	def findMaxSum(self, N, M, Mat):
		i = j = s = 0
		m = Mat[0][0]
		if N >= 3 and M >= 3:
			while i + 2 < N:
				while j + 2 < M:
					s += Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
					if s > m:
						m = s
					j += 1
					s = 0
				i += 1
				j = 0
			return m
		return -1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			B = list(map(int, input().strip().split(' ')))
			Mat.append(B)
		ob = Solution()
		ans = ob.findMaxSum(N, M, Mat)
		print(ans)


class Solution:

	def findMaxSum(self, N, M, mat):
		s = -1
		for i in range(N - 2):
			for j in range(M - 2):
				s = max(s, mat[i][j] + mat[i][j + 1] + mat[i][j + 2] + mat[i + 1][j + 1] + mat[i + 2][j] + mat[i + 2][j + 1] + mat[i + 2][j + 2])
		return s
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			B = list(map(int, input().strip().split(' ')))
			Mat.append(B)
		ob = Solution()
		ans = ob.findMaxSum(N, M, Mat)
		print(ans)


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		m = 0
		for i in range(N - 2):
			for j in range(M - 2):
				s = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 2]
				if s > m:
					m = s
		return m


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		hour_sum = -100 * N * M
		for i in range(N - 2):
			for j in range(M - 2):
				sum_ = sum(Mat[i][j:j + 3]) + Mat[i + 1][j + 1] + sum(Mat[i + 2][j:j + 3])
				hour_sum = max(hour_sum, sum_)
		return hour_sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		s = -math.inf
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				s = max(s, Mat[i - 1][j - 1] + Mat[i - 1][j] + Mat[i - 1][j + 1] + Mat[i][j] + Mat[i + 1][j - 1] + Mat[i + 1][j] + Mat[i + 1][j + 1])
		return s


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		sum = -99999999
		for i in range(0, N - 2):
			for j in range(0, M - 2):
				SUM = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				if SUM > sum:
					sum = SUM
		return sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		max_sum = -1
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				sum = Mat[i - 1][j - 1] + Mat[i - 1][j] + Mat[i - 1][j + 1] + Mat[i][j] + Mat[i + 1][j - 1] + Mat[i + 1][j] + Mat[i + 1][j + 1]
				max_sum = max(max_sum, sum)
		return max_sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		max_sum = 0
		for i in range(N - 2):
			for x in range(M - 2):
				row1 = Mat[i][x] + Mat[i][x + 1] + Mat[i][x + 2]
				row2 = Mat[i + 1][x + 1]
				row3 = Mat[i + 2][x] + Mat[i + 2][x + 1] + Mat[i + 2][x + 2]
				total = row1 + row2 + row3
				max_sum = max(max_sum, total)
		return max_sum


class Solution:

	def findMaxSum(self, N, M, Mat):
		msum = -1
		for i in range(0, len(Mat) - 2):
			for j in range(0, len(Mat[0]) - 2):
				res = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				msum = max(msum, res)
		return msum


class Solution:

	def findMaxSum(self, N, M, a):
		if N < 3 or M < 3:
			return -1
		maxS = -float('inf')
		for i in range(N - 2):
			for j in range(M - 2):
				s = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j + 1] + a[i + 2][j] + a[i + 2][j + 1] + a[i + 2][j + 2]
				maxS = max(s, maxS)
		return maxS


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		maxi = -1
		for i in range(N - 2):
			for j in range(M - 2):
				total = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				maxi = max(maxi, total)
		return maxi


class Solution:

	def findMaxSum(self, N, M, Mat):
		MAX = -1
		SUM = 0
		for i in range(N - 2):
			SUM = 0
			for j in range(M - 2):
				SUM = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				MAX = max(MAX, SUM)
		return MAX


class Solution:

	def findMaxSum(self, N, M, Mat):
		MAX = -9999999999
		SUM = 0
		for i in range(N - 2):
			SUM = 0
			for j in range(M - 2):
				SUM = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
				MAX = max(MAX, SUM)
		if N < 3 or M < 3:
			return -1
		else:
			return MAX


class Solution:

	def findMaxSum(self, N, M, Mat):
		res = -1
		if N < 3 or M < 3:
			return res
		for j in range(M):
			if M - 1 - j >= 2:
				for i in range(N):
					if N - 1 - i >= 2:
						summ = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2]
						if summ > res:
							res = summ
					else:
						break
		return res


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N < 3 or M < 3:
			return -1
		maxi = 0
		for i in range(len(Mat) - 2):
			for j in range(len(Mat[0]) - 2):
				sum_ = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
				maxi = max(maxi, sum_)
		return maxi


class Solution:

	def findMaxSum(self, N, M, arr):
		maxsum = -78
		if N < 3 or M < 3:
			return -1
		for i in range(N - 2):
			for j in range(M - 2):
				sums = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1] + arr[i + 2][j] + arr[i + 2][j + 1] + arr[i + 2][j + 2]
				if sums > maxsum:
					maxsum = sums
		return maxsum


class Solution:

	def findMaxSum(self, N, M, mat):
		if N < 3 or M < 3:
			return -1
		maxSum = 0
		for r in range(N):
			for c in range(M):
				if r < N - 2 and c < M - 2:
					maxSum = max(maxSum, mat[r][c] + mat[r][c + 1] + mat[r][c + 2] + mat[r + 1][c + 1] + mat[r + 2][c] + mat[r + 2][c + 1] + mat[r + 2][c + 2])
		return maxSum


class Solution:

	def findMaxSum(self, N, M, mat):
		ans = 0
		if N < 3 or M < 3:
			return -1
		for i in range(N - 2):
			s = 0
			for j in range(M - 2):
				s = 0
				s += mat[i][j]
				s += mat[i][j + 1]
				s += mat[i][j + 2]
				s += mat[i + 1][j + 1]
				s += mat[i + 2][j]
				s += mat[i + 2][j + 1]
				s += mat[i + 2][j + 2]
				ans = max(ans, s)
		return ans


class Solution:

	def findMaxSum(self, N, M, Mat):
		if N >= 3 and M >= 3:
			tot = 0
			i = 0
			while i < N:
				j = 0
				while j < M:
					if i + 2 < N and j + 2 < M:
						val1 = Mat[i][j]
						val2 = Mat[i][j + 1]
						val3 = Mat[i][j + 2]
						val4 = Mat[i + 1][j + 1]
						val5 = Mat[i + 2][j]
						val6 = Mat[i + 2][j + 1]
						val7 = Mat[i + 2][j + 2]
						count_val = val1 + val2 + val3 + val4 + val5 + val6 + val7
						if tot < count_val:
							tot = count_val
					j += 1
				i += 1
			return tot
		else:
			return -1


class Solution:

	def findMaxSum(self, N, M, arr):
		if N < 3 or M < 3:
			return -1
		else:
			maxx = hgsum(arr, 0, 0)
			for i in range(N - 2):
				for j in range(M - 2):
					cur = hgsum(arr, i, j)
					if cur > maxx:
						maxx = cur
			return maxx

def hgsum(arr, i, j):
	summ = 0
	for a in range(j, j + 3):
		summ += arr[i][a] + arr[i + 2][a]
	summ += arr[i + 1][j + 1]
	return summ


def getSum(x, y, Mat):
	sm = 0
	sm += Mat[x][y] + Mat[x][y + 1] + Mat[x][y + 2]
	sm += Mat[x + 1][y + 1]
	sm += Mat[x + 2][y] + Mat[x + 2][y + 1] + Mat[x + 2][y + 2]
	return sm

class Solution:

	def findMaxSum(self, N, M, Mat):
		if N <= 2 or M <= 2:
			return -1
		sm = 0
		for i in range(N - 2):
			for j in range(M - 2):
				sm = max(sm, getSum(i, j, Mat))
		return sm


class Solution:

	def findMaxSum(self, N, M, Mat):
		self.N = N
		self.M = M
		self.Mat = Mat
		Max_Sum = -5000
		if N < 3 or M < 3:
			return -1
		else:
			for i in range(0, N - 2):
				for j in range(0, M - 2):
					Sum = Mat[i][j] + Mat[i][j + 1] + Mat[i][j + 2] + Mat[i + 1][j + 1] + (Mat[i + 2][j] + Mat[i + 2][j + 1] + Mat[i + 2][j + 2])
					if Sum > Max_Sum:
						Max_Sum = Sum
					else:
						continue
			return Max_Sum