In Geekland there is a grid of coins of size N x N. You have to find the maximum sum of coins in any sub-grid of size K x K.
Note: Coins of the negative denomination are also possible at Geekland.
Example 1:
Input: N = 5, K = 3 
mat[[]] = {1, 1, 1, 1, 1} 
          {2, 2, 2, 2, 2} 
          {3, 8, 6, 7, 3} 
          {4, 4, 4, 4, 4} 
          {5, 5, 5, 5, 5}
Output: 48
Explanation: {8, 6, 7}
             {4, 4, 4}
             {5, 5, 5}
has the maximum sum
Example 2:
Input: N = 1, K = 1
mat[[]] = {{4}} 
Output: 4
Your Task:  
You don't need to read input or print anything. Complete the function Maximum_Sum() which takes the matrix mat[], size of Matrix N, and value K as input parameters and returns the maximum sum.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ K ≤ N ≤ 10^{3}
-5*10^{5} ≤ mat[i][j] ≤ 5*10^{5}

Difficulty: MEDIUM
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})

Starter code:
#User function Template for python3



class Solution:

    def Maximum_Sum(self, mat, N, K):

        # Your code goes here

Solutions:
class Solution:

	def Maximum_Sum(self, mat, N, K):
		prefix = [[0 for i in range(N)] for j in range(N)]
		prefix[0][0] = mat[0][0]
		for i in range(1, N):
			prefix[0][i] += prefix[0][i - 1] + mat[0][i]
			prefix[i][0] += mat[i][0] + prefix[i - 1][0]
		m = -1
		for i in range(1, N):
			for j in range(1, N):
				prefix[i][j] = prefix[i][j - 1] + (prefix[i - 1][j] - prefix[i - 1][j - 1]) + mat[i][j]
		m = float('-inf')
		for i in range(N):
			for j in range(N):
				mat[i][j] = prefix[i][j]
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				if i > K - 1:
					prefix[i][j] -= mat[i - K][j]
				if j > K - 1:
					prefix[i][j] -= mat[i][j - K]
				if i > K - 1 and j > K - 1:
					prefix[i][j] += mat[i - K][j - K]
				if prefix[i][j] > m:
					m = prefix[i][j]
		return m


class Solution:

	def Maximum_Sum(self, mat, N, K):
		prefix = [[0 for _ in range(N)] for _ in range(N)]
		prefix[0][0] = mat[0][0]
		for i in range(1, N):
			prefix[0][i] = prefix[0][i - 1] + mat[0][i]
			prefix[i][0] = prefix[i - 1][0] + mat[i][0]
		for i in range(1, N):
			for j in range(1, N):
				prefix[i][j] = mat[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]
		ans = -int(1000000000.0)
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				temp = prefix[i][j]
				if i - K >= 0:
					temp -= prefix[i - K][j]
				if j - K >= 0:
					temp -= prefix[i][j - K]
				if i - K >= 0 and j - K >= 0:
					temp += prefix[i - K][j - K]
				ans = max(ans, temp)
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(1, N):
			mat[0][i] += mat[0][i - 1]
			mat[i][0] += mat[i - 1][0]
		for i in range(1, N):
			for j in range(1, N):
				mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]
		maxi = mat[K - 1][K - 1]
		for i in range(K, N):
			maxi = max(maxi, mat[i][K - 1] - mat[i - K][K - 1])
			maxi = max(maxi, mat[K - 1][i] - mat[K - 1][i - K])
		for i in range(K, N):
			for j in range(K, N):
				maxi = max(maxi, mat[i][j] + mat[i - K][j - K] - mat[i][j - K] - mat[i - K][j])
		return maxi


def calsum(mat, n):
	temp = [[0 for i in range(n)] for j in range(n)]
	temp[0][0] = mat[0][0]
	for i in range(1, n):
		temp[0][i] = mat[0][i] + temp[0][i - 1]
	for i in range(1, n):
		temp[i][0] = temp[i - 1][0] + mat[i][0]
	for i in range(1, n):
		for j in range(1, n):
			temp[i][j] = mat[i][j] + temp[i - 1][j] + temp[i][j - 1] - temp[i - 1][j - 1]
	return temp

class Solution:

	def Maximum_Sum(self, mat, n, k):
		temp = calsum(mat, n)
		maximum = -999999
		for i in range(k - 1, n):
			for j in range(k - 1, n):
				total = temp[i][j]
				if i - k >= 0:
					total = total - temp[i - k][j]
				if j - k >= 0:
					total = total - temp[i][j - k]
				if i - k >= 0 and j - k >= 0:
					total = total + temp[i - k][j - k]
				if total > maximum:
					maximum = total
		return maximum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]
		res = -100000000.0
		for i in range(K, N + 1):
			for j in range(K, N + 1):
				res = max(res, dp[i][j] - dp[i - K][j] - dp[i][j - K] + dp[i - K][j - K])
		return res


class Solution:

	def Maximum_Sum(self, m, n, k):
		store = [[0 for i in range(n)] for i in range(n - k + 1)]
		for j in range(n):
			s = 0
			for i in range(k):
				s += m[i][j]
			store[0][j] = s
			for i in range(1, n - k + 1):
				s = s - m[i - 1][j] + m[i + k - 1][j]
				store[i][j] = s
		a = []
		for i in range(n - k + 1):
			s = 0
			for j in range(k):
				s += store[i][j]
			a.append(s)
			for j in range(1, n - k + 1):
				s = s - store[i][j - 1] + store[i][j + k - 1]
				a.append(s)
		return max(a)


class Solution:

	def Maximum_Sum(self, mat, n, k):
		dp = [[-1000000 for i in range(n)] for j in range(n)]
		sm = 0
		for i in range(n):
			sm = 0
			for j in range(n):
				if j < k:
					sm = sm + mat[i][j]
					if j == k - 1:
						dp[i][j] = sm
				else:
					sm = sm + mat[i][j] - mat[i][j - k]
					dp[i][j] = sm
		dp1 = [[-1000000 for i in range(n)] for j in range(n)]
		for i in range(n):
			sm = 0
			for j in range(n):
				if j < k:
					sm = sm + dp[j][i]
					if j == k - 1:
						dp1[j][i] = sm
				else:
					sm = sm + dp[j][i] - dp[j - k][i]
					dp1[j][i] = sm
		mx = -1000000
		for i in range(n):
			for j in range(n):
				mx = max(mx, dp1[i][j])
		return mx


class Solution:

	def Maximum_Sum(self, mat, N, K):

		def f(temp, k, N):
			l = 0
			h = 0
			su = 0
			maxi = -1000000000.0
			while h < k:
				su += temp[h]
				h += 1
			maxi = max(maxi, su)
			while h < N:
				su += temp[h] - temp[l]
				h += 1
				l += 1
				maxi = max(maxi, su)
			return maxi
		temp = [0] * N
		for i in range(k):
			for j in range(N):
				temp[j] += mat[i][j]
		l = 0
		h = K
		maxi = -1000000000.0
		maxi = max(maxi, f(temp, K, N))
		while h < N:
			for i in range(N):
				temp[i] += mat[h][i] - mat[l][i]
			maxi = max(maxi, f(temp, K, N))
			h += 1
			l += 1
		return maxi


class Solution:

	def Maximum_Sum(self, mat, N, K):
		ans = -55664651
		for i in range(N):
			for j in range(N):
				if j - 1 >= 0:
					mat[i][j] += mat[i][j - 1]
				if i - 1 >= 0:
					mat[i][j] += mat[i - 1][j]
				if j - 1 >= 0 and i - 1 >= 0:
					mat[i][j] -= mat[i - 1][j - 1]
		for i in range(k - 1, N):
			for j in range(k - 1, N):
				local = mat[i][j]
				if i - k >= 0:
					local -= mat[i - k][j]
				if j - k >= 0:
					local -= mat[i][j - k]
				if i - k >= 0 and j - k >= 0:
					local += mat[i - k][j - k]
				ans = max(ans, local)
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		cp = mat.copy()
		for i in range(N):
			for j in range(1, N):
				cp[i][j] += cp[i][j - 1]
		for j in range(N):
			for i in range(1, N):
				cp[i][j] += cp[i - 1][j]
		maxi = -1000000000000.0
		for i in range(N - K + 1):
			for j in range(N - K + 1):
				ro = i + K - 1
				co = j + K - 1
				sumi = cp[ro][co]
				if j > 0:
					sumi -= cp[ro][j - 1]
				if i > 0:
					sumi -= cp[i - 1][co]
				if i > 0 and j > 0:
					sumi += cp[i - 1][j - 1]
				maxi = max(sumi, maxi)
		return maxi


class Solution:

	def Maximum_Sum(self, mat, N, K):
		arr = mat
		n = N
		k = K
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(n):
				if i == 0:
					dp[i][j] = arr[i][j]
				elif i - k >= 0:
					dp[i][j] = dp[i - 1][j] + arr[i][j] - arr[i - k][j]
				else:
					dp[i][j] = dp[i - 1][j] + arr[i][j]
		ans = [[0] * n for i in range(n)]
		maxval = -10000000
		for i in range(k - 1, n):
			for j in range(n):
				if j == 0:
					ans[i][j] = dp[i][j]
				elif j - k >= 0:
					ans[i][j] = dp[i][j] + ans[i][j - 1] - dp[i][j - k]
				else:
					ans[i][j] = dp[i][j] + ans[i][j - 1]
				if j - k >= -1:
					maxval = max(maxval, ans[i][j])
		return maxval
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		matrix = []
		for _ in range(n):
			matrix.append([int(x) for x in input().strip().split()])
		k = int(input())
		obj = Solution()
		print(obj.Maximum_Sum(matrix, n, k))


def calsum(mat, n):
	temp = [[0 for i in range(n)] for j in range(n)]
	temp[0][0] = mat[0][0]
	for i in range(1, n):
		temp[0][i] = mat[0][i] + temp[0][i - 1]
	for i in range(1, n):
		temp[i][0] = temp[i - 1][0] + mat[i][0]
	for i in range(1, n):
		for j in range(1, n):
			temp[i][j] = mat[i][j] + temp[i - 1][j] + temp[i][j - 1] - temp[i - 1][j - 1]
	return temp

class Solution:

	def Maximum_Sum(self, mat, n, k):
		temp = calsum(mat, n)
		maximum = -999999
		for i in range(k - 1, n):
			for j in range(k - 1, n):
				total = temp[i][j]
				if i - k >= 0:
					total = total - temp[i - k][j]
				if j - k >= 0:
					total = total - temp[i][j - k]
				if i - k >= 0 and j - k >= 0:
					total = total + temp[i - k][j - k]
				if total > maximum:
					maximum = total
		return maximum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		matrix = []
		for _ in range(n):
			matrix.append([int(x) for x in input().strip().split()])
		k = int(input())
		obj = Solution()
		print(obj.Maximum_Sum(matrix, n, k))


class Solution:

	def Maximum_Sum(self, mat, N, K):
		start = 0
		for i in range(K):
			for j in range(K):
				start += mat[i][j]
		dp = [[0 for j in range(N)] for i in range(N)]
		dp[K - 1][K - 1] = start
		rowSum = [[y for y in x] for x in mat]
		colSum = [[y for y in x] for x in mat]
		for i in range(N):
			for j in range(N):
				if j > 0:
					rowSum[i][j] += rowSum[i][j - 1]
				if i > 0:
					colSum[i][j] += colSum[i - 1][j]
		res = start
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				if j == K - 1:
					if i == K - 1:
						continue
					prev = dp[i - 1][j]
					addRow = rowSum[i][j]
					removeRow = rowSum[i - K][j]
					dp[i][j] = prev + addRow - removeRow
					res = max(res, dp[i][j])
					continue
				prev = dp[i][j - 1]
				addCol = colSum[i][j] - (colSum[i - K][j] if i - K >= 0 else 0)
				removeCol = colSum[i][j - K] - (colSum[i - K][j - K] if i - K >= 0 else 0)
				dp[i][j] = prev + addCol - removeCol
				res = max(res, dp[i][j])
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		matrix = []
		for _ in range(n):
			matrix.append([int(x) for x in input().strip().split()])
		k = int(input())
		obj = Solution()
		print(obj.Maximum_Sum(matrix, n, k))


class Solution:

	def Maximum_Sum(self, mat, N, K):
		ps = [[0 for _ in range(N)] for _ in range(N)]
		s = s2 = 0
		for i in range(N):
			s += mat[i][0]
			s2 += mat[0][i]
			ps[i][0] = s
			ps[0][i] = s2
		for i in range(1, N):
			for j in range(1, N):
				ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + mat[i][j]
		maxi = -float('inf')
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				x = y = z = 0
				if i - K >= 0:
					x = ps[i - K][j]
				if j - K >= 0:
					y = ps[i][j - K]
				if i - K >= 0 and j - K >= 0:
					z = ps[i - K][j - K]
				s = ps[i][j] - x - y + z
				maxi = max(maxi, s)
		return maxi


class Solution:

	def Maximum_Sum(self, mat, n, k):
		prefix_sum = [[0 for i in range(n)] for j in range(n)]
		res = [[float('-inf') for j in range(n)] for i in range(n)]
		max_sum = float('-inf')
		for i in range(n):
			for j in range(n):
				if i == 0 and j == 0:
					prefix_sum[i][j] = mat[i][j]
				if i == 0 and j > 0:
					prefix_sum[i][j] = prefix_sum[i][j - 1] + mat[i][j]
				if j == 0 and i > 0:
					prefix_sum[i][j] = prefix_sum[i - 1][j] + mat[i][j]
				if i > 0 and j > 0:
					prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + mat[i][j]
		for i in range(n):
			for j in range(n):
				if i - k < -1 or j - k < -1:
					continue
				if i - k == -1 and j - k == -1:
					res[i][j] = prefix_sum[i][j]
					max_sum = max(max_sum, res[i][j])
				if i - k == -1 and j - k >= 0:
					res[i][j] = prefix_sum[i][j] - prefix_sum[i][j - k]
					max_sum = max(max_sum, res[i][j])
				if i - k >= 0 and j - k == -1:
					res[i][j] = prefix_sum[i][j] - prefix_sum[i - k][j]
					max_sum = max(max_sum, res[i][j])
				if i - k >= 0 and j - k >= 0:
					res[i][j] = prefix_sum[i][j] - prefix_sum[i - k][j] - prefix_sum[i][j - k] + prefix_sum[i - k][j - k]
					max_sum = max(max_sum, res[i][j])
		return max_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		col_sum = [[0] * N for i in range(N)]
		for j in range(N):
			for i in range(K):
				col_sum[i][j] = mat[i][j] + (col_sum[i - 1][j] if i > 0 else 0)
		for j in range(N):
			for i in range(K, N):
				col_sum[i][j] = mat[i][j] + col_sum[i - 1][j] - mat[i - K][j]
		max_sum = float('-inf')
		for i in range(K - 1, N):
			grid_sum = 0
			for j in range(K - 1):
				grid_sum += col_sum[i][j]
			for j in range(K - 1, N):
				grid_sum += col_sum[i][j]
				if j >= K:
					grid_sum -= col_sum[i][j - K]
				max_sum = max(max_sum, grid_sum)
		return max_sum


import sys

class Solution:

	def Maximum_Sum(self, mat, N, K1):
		mat1 = []
		mat2 = []
		for i in range(0, N):
			k = 0
			p = []
			for j in range(0, N):
				k += mat[i][j]
				p.append(k)
			mat1.append(p)
		for i in range(0, N):
			k = 0
			for j in range(0, N):
				k += mat1[j][i]
				mat1[j][i] = k
		ma = -sys.maxsize - 1
		for i in range(0, N - K1 + 1):
			for j in range(0, N - K1 + 1):
				if i == 0 and j == 0:
					p1 = mat1[i + (K1 - 1)][j + (K1 - 1)]
					if p1 > ma:
						ma = p1
				elif i == 0 and j > 0:
					p1 = mat1[i + (K1 - 1)][j + (K1 - 1)]
					q1 = mat1[i + (K1 - 1)][j - 1]
					if p1 - q1 > ma:
						ma = p1 - q1
				elif i > 0 and j == 0:
					p1 = mat1[i + (K1 - 1)][j + (K1 - 1)]
					q1 = mat1[i - 1][j + (K1 - 1)]
					if p1 - q1 > ma:
						ma = p1 - q1
				else:
					p1 = mat1[i + (K1 - 1)][j + (K1 - 1)]
					q1 = mat1[i + (K1 - 1)][j - 1]
					r1 = mat1[i - 1][j + (K1 - 1)]
					m1 = mat1[i - 1][j - 1]
					res = p1 - (q1 - m1 + r1)
					if res > ma:
						ma = res
		return ma


class Solution:

	def Maximum_Sum(self, mat, N, k):
		if k > N:
			return
		stripSum = [[0 for j in range(N)] for i in range(N)]
		for j in range(N):
			sum = 0
			for i in range(k):
				sum += mat[i][j]
			stripSum[0][j] = sum
			for i in range(1, N - k + 1):
				sum += mat[i + k - 1][j] - mat[i - 1][j]
				stripSum[i][j] = sum
		max_sum = -1000000000
		i_ind = 0
		j_ind = 0
		for i in range(N - k + 1):
			sum = 0
			for j in range(k):
				sum += stripSum[i][j]
			if sum > max_sum:
				max_sum = sum
				i_ind = i
				j_ind = 0
			for j in range(1, N - k + 1):
				sum += stripSum[i][j + k - 1] - stripSum[i][j - 1]
				if sum > max_sum:
					max_sum = sum
					i_ind = i
					j_ind = j
		return max_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		pref = mat.copy()
		for i in range(1, N):
			pref[0][i] += pref[0][i - 1]
			pref[i][0] += pref[i - 1][0]
		for i in range(1, N):
			for j in range(1, N):
				pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]
		mx = -999999999999999
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				k = pref[i][j]
				if i - K >= 0:
					k -= pref[i - K][j]
				if j - K >= 0:
					k -= pref[i][j - K]
				if i - K >= 0 and j - K >= 0:
					k += pref[i - K][j - K]
				mx = max(mx, k)
		return mx


import sys

class Solution:

	def Maximum_Sum(self, mat, n, k):
		ans = -sys.maxsize
		for i in range(n):
			for j in range(n):
				if i - 1 >= 0:
					mat[i][j] = mat[i][j] + mat[i - 1][j]
				if j - 1 >= 0:
					mat[i][j] = mat[i][j] + mat[i][j - 1]
				if i - 1 >= 0 and j - 1 >= 0:
					mat[i][j] = mat[i][j] - mat[i - 1][j - 1]
		for i in range(k - 1, n):
			for j in range(k - 1, n):
				curSum = mat[i][j]
				if i - k >= 0:
					curSum -= mat[i - k][j]
				if j - k >= 0:
					curSum -= mat[i][j - k]
				if i - k >= 0 and j - k >= 0:
					curSum += mat[i - k][j - k]
				ans = max(ans, curSum)
		return ans


import sys

class Solution:

	def Maximum_Sum(self, arr, N, K):
		m = n
		ans = -sys.maxsize
		sum = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				sum[i][j] = arr[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]
		for i in range(k, n + 1):
			for j in range(k, n + 1):
				curSum = sum[i][j]
				if i - k >= 0:
					curSum -= sum[i - k][j]
				if j - k >= 0:
					curSum -= sum[i][j - k]
				if i - k >= 0 and j - k >= 0:
					curSum += sum[i - k][j - k]
				ans = max(ans, curSum)
		return ans


import sys

class Solution:

	def Maximum_Sum(self, mat, N, K):
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		max_sum = -sys.maxsize
		for i in range(K, N + 1):
			for j in range(K, N + 1):
				sum = dp[i][j]
				if i - K >= 0:
					sum -= dp[i - K][j]
				if j - K >= 0:
					sum -= dp[i][j - K]
				if i - K >= 0 and j - K >= 0:
					sum += dp[i - K][j - K]
				max_sum = max(max_sum, sum)
		return max_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(1, N):
			for j in range(N):
				mat[i][j] += mat[i - 1][j]
		ans = -2 ** 63 + 1
		dp = [[0] * N for i in range(N)]
		start = 0
		for i in range(K):
			for j in range(N):
				dp[i][j] = mat[i][j]
		for i in range(K, N):
			for j in range(N):
				dp[i][j] = mat[i][j] - mat[start][j]
			start += 1
		for i in range(K - 1, N):
			for j in range(N - K + 1):
				ans = max(ans, sum(dp[i][j:j + K]))
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		psa = [[0 for i in range(N)] for j in range(N)]
		psa[0][0] = mat[0][0]
		for i in range(1, N):
			psa[i][0] = psa[i - 1][0] + mat[i][0]
		for j in range(1, N):
			psa[0][j] = psa[0][j - 1] + mat[0][j]
		for i in range(1, N):
			for j in range(1, N):
				psa[i][j] = mat[i][j] + psa[i - 1][j] + psa[i][j - 1] - psa[i - 1][j - 1]
		max_sum = float('-inf')
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				tmp = psa[i][j]
				if i - K >= 0 and j - K >= 0:
					tmp = tmp - psa[i - K][j] - psa[i][j - K] + psa[i - K][j - K]
				elif i - K >= 0:
					tmp = tmp - psa[i - K][j]
				elif j - K >= 0:
					tmp = tmp - psa[i][j - K]
				if tmp > max_sum:
					max_sum = tmp
		return max_sum


def window(arr, l):
	m = 0
	mx = -float('inf')
	s = 0
	for i in range(l):
		m += arr[i]
	mx = max(mx, m)
	for i in range(l, len(arr)):
		m -= arr[s]
		m += arr[i]
		mx = max(mx, m)
		s += 1
	return mx

class Solution:

	def Maximum_Sum(self, mat, N, k):
		m = len(mat)
		n = len(mat[0])
		temp = [0] * n
		for i in range(k):
			for j in range(n):
				temp[j] += mat[i][j]
		mx = -float('inf')
		mx = max(mx, window(temp, k))
		s = 0
		for i in range(k, m):
			for j in range(n):
				temp[j] -= mat[s][j]
				temp[j] += mat[i][j]
			s += 1
			mx = max(mx, window(temp, k))
		return mx


class Solution:

	def Maximum_Sum(self, mat, N, K):
		store = [[0] * (N + 1) for i in range(N + 1)]
		for i in range(N):
			for j in range(N):
				if i >= 1:
					mat[i][j] += mat[i - 1][j]
				if j >= 1:
					mat[i][j] += mat[i][j - 1]
				if i >= 1 and j >= 1:
					mat[i][j] -= mat[i - 1][j - 1]
		ans = -float('inf')
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				local = mat[i][j]
				if i - K >= 0:
					local -= mat[i - K][j]
				if j - K >= 0:
					local -= mat[i][j - K]
				if i - K >= 0 and j - K >= 0:
					local += mat[i - K][j - K]
				ans = max(ans, local)
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(N):
			for j in range(1, N):
				mat[i][j] += mat[i][j - 1]
		for i in range(1, N):
			for j in range(N):
				mat[i][j] += mat[i - 1][j]
		ans = 0
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				cur = mat[i][j]
				cur -= mat[i - K][j] if i - K >= 0 else 0
				cur -= mat[i][j - K] if j - K >= 0 else 0
				cur += mat[i - K][j - K] if min(i - K, j - K) >= 0 else 0
				ans = max(ans, cur)
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		sum_matrix = [[0 for _ in range(N)] for _ in range(N)]
		for r in range(N):
			for c in range(N):
				sum_matrix[r][c] = mat[r][c]
				if r > 0:
					sum_matrix[r][c] += sum_matrix[r - 1][c]
				if c > 0:
					sum_matrix[r][c] += sum_matrix[r][c - 1]
				if r > 0 and c > 0:
					sum_matrix[r][c] -= sum_matrix[r - 1][c - 1]
		ret = 0
		for r in range(K - 1, N):
			for c in range(K - 1, N):
				value = sum_matrix[r][c]
				if r > K - 1:
					value -= sum_matrix[r - K][c]
				if c > K - 1:
					value -= sum_matrix[r][c - K]
				if r > K - 1 and c > K - 1:
					value += sum_matrix[r - K][c - K]
				ret = max(ret, value)
		return ret


class Solution:

	def Maximum_Sum(self, mat, N, K):
		maxsum = -5 * pow(10, 5)
		prefix_mat = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			for j in range(N):
				prefix_mat[i][j] = mat[i][j]
		for i in range(1, N):
			prefix_mat[i][0] += prefix_mat[i - 1][0]
		for j in range(1, N):
			prefix_mat[0][j] += prefix_mat[0][j - 1]
		for i in range(1, N):
			for j in range(1, N):
				prefix_mat[i][j] += prefix_mat[i][j - 1] + prefix_mat[i - 1][j] - prefix_mat[i - 1][j - 1]
		for i in range(k - 1, N):
			for j in range(k - 1, N):
				(rowv, colv, commonval) = (0, 0, 0)
				if j >= k:
					rowv = prefix_mat[i][j - k]
				if i >= k:
					colv = prefix_mat[i - k][j]
				if i >= k and j >= k:
					commonval = prefix_mat[i - k][j - k]
				cursum = prefix_mat[i][j] - rowv - colv + commonval
				maxsum = max(maxsum, cursum)
		return maxsum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(N):
			for j in range(N):
				if i != 0:
					mat[i][j] += mat[i - 1][j]
		for i in range(N):
			for j in range(N):
				if j != 0:
					mat[i][j] += mat[i][j - 1]
		dp = [[0 for i in range(N)] for i in range(N)]
		top = 0
		left = 0
		center = 0
		ans = 0
		for i in range(N):
			for j in range(N):
				top = 0 if i - K < 0 else mat[i - K][j]
				left = 0 if j - K < 0 else mat[i][j - K]
				center = 0 if i < K or j < K else mat[i - k][j - k]
				dp[i][j] = mat[i][j] - top - left + center
				ans = max(ans, dp[i][j])
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		gmax = None
		l1 = [0] * (len(mat[0]) + 1)
		sumgrid = []
		for i in range(len(mat) + 1):
			sumgrid.append(l1[:])
		for i in range(len(mat)):
			sum1 = 0
			for j in range(len(mat[i])):
				sum1 = sum1 + mat[i][j]
				sumgrid[i + 1][j + 1] = sumgrid[i][j + 1] + sum1
		for i in range(1, len(sumgrid)):
			for j in range(1, len(sumgrid)):
				idif = i - k
				jdif = j - k
				if idif >= 0 and jdif >= 0:
					sum1 = sumgrid[i][j] + sumgrid[idif][jdif] - sumgrid[idif][j] - sumgrid[i][jdif]
					if gmax == None:
						gmax = sum1
					elif sum1 > gmax:
						gmax = sum1
					else:
						pass
				else:
					pass
		return gmax


class Solution:

	def Maximum_Sum(self, mat, N, K):
		prefixsum = [[0 for i in range(N)] for m in mat]
		prefixsum[0][0] = mat[0][0]
		for r in range(N):
			currentrow = 0
			for c in range(N):
				currentrow += mat[r][c]
				prefixsum[r][c] = currentrow + (prefixsum[r - 1][c] if r > 0 else 0)

		def sumBlock(i, j, pre):
			if i + K <= N and j + K <= N:
				A = pre[i + K - 1][j + K - 1]
				B = pre[i - 1][j + K - 1] if i > 0 else 0
				C = pre[i + K - 1][j - 1] if j > 0 else 0
				D = pre[i - 1][j - 1] if i > 0 and j > 0 else 0
				return A - B - C + D
			else:
				return -2 ** 32
		bestsub = -2 ** 32
		for r in range(N - K + 1):
			for c in range(N - K + 1):
				block = sumBlock(r, c, prefixsum)
				bestsub = max(bestsub, block)
		return bestsub


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(N):
			for j in range(N):
				if i - 1 >= 0:
					mat[i][j] += mat[i - 1][j]
				if j - 1 >= 0:
					mat[i][j] += mat[i][j - 1]
				if i - 1 >= 0 and j - 1 >= 0:
					mat[i][j] -= mat[i - 1][j - 1]
		maximum = -9999999999999999
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				temp = mat[i][j]
				if i - K >= 0:
					temp -= mat[i - K][j]
				if j - K >= 0:
					temp -= mat[i][j - K]
				if i - K >= 0 and j - K >= 0:
					temp += mat[i - K][j - K]
				maximum = maximum if maximum > temp else temp
		return maximum


import sys

class Solution:

	def Maximum_Sum(self, mat, N, K):
		sum_arr = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			for j in range(N):
				if i > 0 and j > 0:
					sum_arr[i][j] = sum_arr[i - 1][j] + sum_arr[i][j - 1] + mat[i][j] - sum_arr[i - 1][j - 1]
				elif i > 0:
					sum_arr[i][j] = sum_arr[i - 1][j] + mat[i][j]
				elif j > 0:
					sum_arr[i][j] = sum_arr[i][j - 1] + mat[i][j]
				else:
					sum_arr[i][j] = mat[i][j]
		max_value = 1 - sys.maxsize
		for i in range(N):
			for j in range(N):
				k_sum = sum_arr[i][j]
				if i - K >= 0:
					k_sum -= sum_arr[i - K][j]
				if j - K >= 0:
					k_sum -= sum_arr[i][j - K]
				if i - K >= 0 and j - K >= 0:
					k_sum += sum_arr[i - K][j - K]
				if k_sum > max_value:
					max_value = k_sum
		return max_value


class Solution:

	def Maximum_Sum(self, mat, N, K):
		maximum_sum = 0
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				else:
					dp[i][j] = mat[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
				if i >= k and j >= k:
					maximum_sum = max(dp[i][j] - (dp[i][j - k] + dp[i - k][j] - dp[i - k][j - k]), maximum_sum)
		return maximum_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		max_sum = 0
		s = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			for j in range(n):
				s[i + 1][j + 1] = mat[i][j]
				s[i + 1][j + 1] += s[i][j + 1]
				s[i + 1][j + 1] += s[i + 1][j]
				s[i + 1][j + 1] -= s[i][j]
				if i >= k - 1 and j >= k - 1:
					max_sum = max(s[i + 1][j + 1] - s[i + 1][j - k + 1] - s[i - k + 1][j + 1] + s[i - k + 1][j - k + 1], max_sum)
		return max_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		temp = [[-1 for i in range(0, N)] for i in range(0, N)]
		for ind in range(0, N):
			(i, j) = (0, 0)
			summ = 0
			while j < n:
				summ += mat[ind][j]
				if j - i + 1 == K:
					temp[ind][j] = summ
					summ -= mat[ind][i]
					i += 1
				j += 1
		maxx = -float('inf')
		for ind in range(0, N):
			(i, j) = (0, 0)
			summ = 0
			while j < n:
				summ += temp[j][ind]
				if j - i + 1 == K:
					maxx = max(maxx, summ)
					summ -= temp[i][ind]
					i += 1
				j += 1
		return maxx


import sys

class Solution:

	def getSum(self, mat, n):
		for i in range(n):
			for j in range(n):
				(top, left, daigonal) = (0, 0, 0)
				if i - 1 >= 0:
					top = mat[i - 1][j]
				if j - 1 >= 0:
					left = mat[i][j - 1]
				if i - 1 >= 0 and j - 1 >= 0:
					daigonal = mat[i - 1][j - 1]
				mat[i][j] = top + left - daigonal + mat[i][j]

	def Maximum_Sum(self, mat, N, K):
		maxSum = [-sys.maxsize]
		self.getSum(mat, N)
		for i in range(N - K + 1):
			for j in range(N - K + 1):
				end_row = i + K - 1
				end_col = j + K - 1
				(top, left, daigonal) = (0, 0, 0)
				if i - 1 >= 0:
					top = mat[i - 1][end_col]
				if j - 1 >= 0:
					left = mat[end_row][j - 1]
				if i - 1 >= 0 and j - 1 >= 0:
					daigonal = mat[i - 1][j - 1]
				s = mat[end_row][end_col]
				s = s - top - left + daigonal
				maxSum[0] = max(s, maxSum[0])
		return maxSum[0]


class Solution:

	def Maximum_Sum(self, mat, n, k):

		def get(x, y):
			if x < 0 or y < 0:
				return 0
			return mat[x][y]

		def calc(x, y, d, m=1):
			return get(x, y) + get(x - d, y) * m + get(x, y - d) * m - get(x - d, y - d) * m
		for i in range(n):
			for j in range(n):
				mat[i][j] = calc(i, j, 1)
		res = -float('inf')
		for i in range(k - 1, n):
			for j in range(k - 1, n):
				cur = calc(i, j, k, -1)
				res = max(cur, res)
		return res


class Solution:

	def Maximum_Sum(self, mat, n, k):
		mx = -999999
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				dp[i][j] = mat[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
				if i >= k and j >= k:
					mx = max(dp[i][j] - (dp[i - k][j] + dp[i][j - k] - dp[i - k][j - k]), mx)
		return mx


class Solution:

	def Maximum_Sum(self, mat, n, k):

		def get(x, y):
			if x < 0 or y < 0:
				return 0
			return mat[x][y]

		def calc(x, y):
			up = get(x - 1, y)
			left = get(x, y - 1)
			diag = get(x - 1, y - 1)
			return up + left - diag
		for i in range(n):
			for j in range(n):
				mat[i][j] += calc(i, j)
		res = -float('inf')
		for i in range(k - 1, n):
			for j in range(k - 1, n):
				cur = mat[i][j]
				if j != k - 1:
					cur -= mat[i][j - k]
				if i != k - 1:
					cur -= mat[i - k][j]
				if i != k - 1 and j != k - 1:
					cur += mat[i - k][j - k]
				res = max(cur, res)
		return res


class Solution:

	def Maximum_Sum(self, mat, N, K):
		if K > N:
			return 0
		tl = []
		max_sum = 0
		i = 0
		while i < N:
			j = 0
			while j < N - K + 1:
				x = i
				t = sum(mat[i][j:j + K])
				tl.append(t)
				j += 1
			i += 1
		f = []
		for l in range(0, (N - K + 1) * (N - K + 1)):
			f.append(sum(tl[l:l + (N - K + 1) * K:N - K + 1]))
		return max(f)


class Solution:

	def Maximum_Sum(self, mat, N, K):
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		ans = 0
		for (i, r) in enumerate(dp):
			for (j, _) in enumerate(r):
				if i > 0 and j > 0:
					dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
				if i >= k and j >= k:
					area = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]
					ans = max(ans, area)
		return ans


import math

class Solution:

	def Maximum_Sum(self, mat, N, K):
		if N == 1:
			return mat[0][0]
		sumContainer = [[0] * N for _ in range(N)]
		for i in range(N):
			sumContainer[i][0] = mat[i][0]
			for j in range(1, N):
				sumContainer[i][j] = sumContainer[i][j - 1] + mat[i][j]
		for i in range(1, N):
			for j in range(N):
				sumContainer[i][j] = sumContainer[i][j] + sumContainer[i - 1][j]
		maxSum = -math.inf
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				totalSumTillIJ = sumContainer[i][j]
				upperBlockSum = 0
				if i >= K:
					upperBlockSum = sumContainer[i - K][j]
				leftBlockSum = 0
				if j >= K:
					leftBlockSum = sumContainer[i][j - K]
				commonBlockSum = 0
				if i >= K and j >= K:
					commonBlockSum = sumContainer[i - K][j - K]
				maxSum = max(maxSum, totalSumTillIJ - leftBlockSum - upperBlockSum + commonBlockSum)
		return maxSum


import sys

class Solution:

	def Maximum_Sum(self, mat, N, K):
		dp = [[0 for i in range(N)] for i in range(N)]
		for i in range(N):
			for j in range(N):
				dp[i][j] = mat[i][j]
				if i > 0:
					dp[i][j] += dp[i - 1][j]
				if j > 0:
					dp[i][j] += dp[i][j - 1]
				if i > 0 and j > 0:
					dp[i][j] -= dp[i - 1][j - 1]
		ans = 0
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				t = dp[i][j]
				if i > K - 1:
					t -= dp[i - K][j]
				if j > K - 1:
					t -= dp[i][j - K]
				if i > K - 1 and j > K - 1:
					t += dp[i - K][j - K]
				ans = max(ans, t)
		return ans


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for (i, _) in enumerate(mat):
			for (j, e) in enumerate(mat[i]):
				if j > 0:
					mat[i][j] += mat[i][j - 1]
				if i > 0:
					mat[i][j] += mat[i - 1][j]
				if i > 0 and j > 0:
					mat[i][j] -= mat[i - 1][j - 1]
		ans = 0
		for y0 in range(0, N - K + 1):
			for x0 in range(0, N - K + 1):
				(y, x) = (y0 + K, x0 + K)
				v = area(mat, y - 1, x - 1) + area(mat, y0 - 1, x0 - 1) - area(mat, y - 1, x0 - 1) - area(mat, y0 - 1, x - 1)
				ans = max(ans, v)
		return ans

def area(mat, y, x):
	if y < 0 or x < 0:
		return 0
	return mat[y][x]


class Solution:

	def Maximum_Sum(self, mat, N, K):
		maxx = 0
		zero_mat = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
		for i in range(N):
			for j in range(N):
				zero_mat[i + 1][j + 1] = mat[i][j]
				zero_mat[i + 1][j + 1] += zero_mat[i][j + 1]
				zero_mat[i + 1][j + 1] += zero_mat[i + 1][j]
				zero_mat[i + 1][j + 1] -= zero_mat[i][j]
				if i >= K - 1 and j >= K - 1:
					maxx = max(zero_mat[i + 1][j + 1] - zero_mat[i + 1][j - K + 1] - zero_mat[i - K + 1][j + 1] + zero_mat[i - K + 1][j - K + 1], maxx)
		return maxx


from typing import List

class Solution:

	def Maximum_Sum(self, mat, N, K):
		if K > N:
			return
		stripSum = [[0 for j in range(N)] for i in range(N)]
		for j in range(N):
			sum = 0
			for i in range(k):
				sum += mat[i][j]
			stripSum[0][j] = sum
			for i in range(1, N - k + 1):
				sum += mat[i + k - 1][j] - mat[i - 1][j]
				stripSum[i][j] = sum
		max_sum = -1000000000
		i_ind = 0
		j_ind = 0
		for i in range(N - k + 1):
			sum = 0
			for j in range(k):
				sum += stripSum[i][j]
			if sum > max_sum:
				max_sum = sum
				i_ind = i
				j_ind = 0
			for j in range(1, N - k + 1):
				sum += stripSum[i][j + k - 1] - stripSum[i][j - 1]
				if sum > max_sum:
					max_sum = sum
					i_ind = i
					j_ind = j
		return max_sum


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(N):
			for j in range(N):
				if i - 1 >= 0:
					mat[i][j] += mat[i - 1][j]
				if j - 1 >= 0:
					mat[i][j] += mat[i][j - 1]
				if j - 1 >= 0 and i - 1 >= 0:
					mat[i][j] -= mat[i - 1][j - 1]
		m = 0
		for i in range(N):
			for j in range(N):
				l = mat[i][j]
				if i - K >= 0:
					l -= mat[i - k][j]
				if j - K >= 0:
					l -= mat[i][j - K]
				if i - K >= 0 and j - K >= 0:
					l += mat[i - k][j - K]
				m = max(m, l)
		return m


from itertools import *

class Solution:

	def Maximum_Sum(self, a, n, t):
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		res = float('-inf')
		for (i, j) in product(range(1, n + 1), range(1, n + 1)):
			dp[i][j] += a[i - 1][j - 1]
			dp[i][j] += dp[i - 1][j]
			dp[i][j] += dp[i][j - 1]
			dp[i][j] -= dp[i - 1][j - 1]
			if i >= t and j >= t:
				res = max(res, dp[i][j] - dp[i - t][j] - dp[i][j - t] + dp[i - t][j - t])
		return res


class Solution:

	def Maximum_Sum(self, mat, N, K):
		dp = [[0] * (N + 1) for i in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if i == 1:
					dp[i][j] = dp[i][j - 1] + mat[i - 1][j - 1]
				elif j == 1:
					dp[i][j] = dp[i - 1][j] + mat[i - 1][j - 1]
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1]
		ma = 0
		for i in range(k, N + 1):
			for j in range(k, N + 1):
				ma = max(ma, dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k])
		return ma


class Solution:

	def Maximum_Sum(self, mat, n, k):
		dp = [[0] * (n + 1) for i in range(n + 1)]
		maxm = -10000000.0
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				else:
					dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
				if i >= k and j >= k:
					maxm = max(maxm, dp[i][j] - (dp[i - k][j] + dp[i][j - k] - dp[i - k][j - k]))
		return maxm


class Solution:

	def Maximum_Sum(self, mat, N, K):
		for i in range(N):
			for j in range(1, N):
				mat[i][j] += mat[i][j - 1]
		for i in range(1, N):
			for j in range(N):
				mat[i][j] += mat[i - 1][j]
		res = mat[K - 1][K - 1]
		for i in range(K - 1, N):
			for j in range(K - 1, N):
				if i == K - 1 and j == K - 1:
					continue
				temp = mat[i][j]
				if i > K - 1:
					temp -= mat[i - K][j]
				if j > K - 1:
					temp -= mat[i][j - K]
				if i > K - 1 and j > K - 1:
					temp += mat[i - K][j - K]
				res = max(res, temp)
		return res


class Solution:

	def Maximum_Sum(self, mat, N, k):
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			for j in range(N):
				if i == 0 and j == 0:
					dp[i][j] = mat[i][j]
				elif i == 0:
					dp[i][j] = mat[i][j] + dp[i][j - 1]
				elif j == 0:
					dp[i][j] = mat[i][j] + dp[i - 1][j]
				else:
					dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		result = float('-inf')
		for i in range(k - 1, N):
			for j in range(k - 1, N):
				if i == k - 1 and j == k - 1:
					result = max(result, dp[i][j])
				elif i == k - 1:
					result = max(result, dp[i][j] - dp[i][j - k])
				elif j == k - 1:
					result = max(result, dp[i][j] - dp[i - k][j])
				else:
					result = max(result, dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k])
		return result


import sys

class Solution:

	def Maximum_Sum(self, mat, N, K):
		mx = -sys.maxsize - 1
		dp = [[0 for x in range(N + 1)] for y in range(N + 1)]
		for i in range(0, N + 1):
			for j in range(0, N + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]
				if i >= k and j >= k:
					mx = max(dp[i][j] - (dp[i - k][j] + dp[i][j - k] - dp[i - k][j - k]), mx)
		return mx


class Solution:

	def Maximum_Sum(self, mat, N, K):
		maxx = 0
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			for j in range(n):
				dp[i + 1][j + 1] = mat[i][j]
				dp[i + 1][j + 1] += dp[i][j + 1]
				dp[i + 1][j + 1] += dp[i + 1][j]
				dp[i + 1][j + 1] -= dp[i][j]
				if i >= k - 1 and j >= k - 1:
					maxx = max(dp[i + 1][j + 1] - dp[i + 1][j - k + 1] - dp[i - k + 1][j + 1] + dp[i - k + 1][j - k + 1], maxx)
		return maxx