Consider an square matrix where each cell contains a binary integer (i.e., a or ). You can perform the following swap operation at most one time:
Choose two rectangular submatrices that do not intersect or overlap and swap them. Note that both submatrices must have the same exact dimensions and you cannot rotate or otherwise change their orientation.
Given an binary matrix, perform at most one swap operation such that the largest submatrix consisting only of 's has a maximal value of . Then print the value of this maximal as your answer.
Input Format
The first line contains a single integer, , denoting the length of the matrix's sides.
Each line of the subsequent lines contains space-separated binary integers describing the respective values of each cell in row of the matrix.
Constraints
Output Format
Print the value of for the maximal submatrix consisting only of 's.
Sample Input
5
1 1 1 0 0
0 0 1 1 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 1
Sample Output
3
Explanation
In the initial matrix, the maximum value is . If we use our swap operation to exchange the contents of two rectangles, we can get a maximal value of (as demonstrated in the diagram above). Thus, we print as our answer.