Maximum Sum Submatrix

You are given a square matrix \(A\) of size \(n \times n\) consisting of integers, and an integer \(k\). Your task is to find the maximum sum of any submatrix of size \(k \times k\) in \(A\). A submatrix is defined as a contiguous block of rows and columns.

If \(k > n\), output \(-1\) since a \(k \times k\) submatrix cannot be extracted. Otherwise, compute the sum for every possible \(k \times k\) submatrix, and output the maximum of these sums.

Input Format: The input is given via standard input as described below.

Output Format: Output the maximum sum computed to standard output.

inputFormat

The first line contains two space-separated integers \(n\) and \(k\), where \(n\) is the number of rows (and columns) of the matrix, and \(k\) is the dimension of the submatrix.

The following \(n\) lines each contain \(n\) space-separated integers representing the rows of the matrix.

outputFormat

Output a single integer which is the maximum sum of any \(k \times k\) submatrix in the matrix. If no such submatrix exists, output \(-1\).

## sample

3 2
1 2 3
4 5 6
7 8 9

28