Maximum Sum of KxK Submatrix

You are given an N x N matrix of integers and a positive integer K. Your task is to find the submatrix of size K x K that has the largest sum of its elements.

The submatrix is a contiguous block of K rows and K columns extracted from the original matrix. Formally, if we denote the matrix by \(A\), you need to find indices \(i\) and \(j\) such that the sum \[ \sum_{x=i}^{i+K-1} \sum_{y=j}^{j+K-1} A[x][y] \] is maximized. Note that \(1 \leq K \leq N\) and indexing is 0-based.

Input format: The first line of input contains two integers N and K. The following N lines each contain N integers representing the rows of the matrix.

Output format: Output a single integer which is the maximum sum of a K x K submatrix found in the given matrix.

inputFormat

The first line contains two space-separated integers, N and K. Each of the next N lines contains N space-separated integers representing the matrix.

outputFormat

Output a single integer — the maximum sum of any KxK submatrix.## sample

4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

54