Matrix Rotation and Maximum Submatrix Sum

You are given a matrix of size R × C and an integer n. Your task is to compute the maximum sum of an n × n submatrix, taken over all four rotations of the matrix (i.e. 0°, 90°, 180°, and 270° rotations). In other words, if you denote the matrix by \(A\), you must consider the matrices \(A\), \(A_{90}\), \(A_{180}\), and \(A_{270}\), and then find:

[ \max{ S(M) : M \in {A, A_{90}, A_{180}, A_{270}} }, ]

where \(S(M)\) is the maximum sum of any contiguous n × n submatrix in matrix \(M\). It is guaranteed that the matrix dimensions are at least \(n\) in both directions.

inputFormat

The first line contains two integers \(R\) and \(C\), representing the number of rows and columns of the matrix respectively.

The next \(R\) lines each contain \(C\) space-separated integers, representing the elements of the matrix.

The last line contains a single integer \(n\), representing the size of the submatrix.

outputFormat

Output a single integer which is the maximum sum of any n × n submatrix among all four rotations of the given matrix.

3 3
1 2 3
4 5 6
7 8 9
2

28