Maximizing Connected Land in a Merging Grid Game

In this problem, Xiaolan is playing a farming game. He is given two square regions of size \(N\times N\), each subdivided into \(N\times N\) identically sized cells. Every cell is either soil or rock. A connected piece of land is defined as a maximal set of soil cells that are adjacent horizontally or vertically (i.e. sharing an edge). 

Xiaolan plans to merge these two regions along one of their edges. The merge must follow these rules:

• The two regions are aligned along their edges (i.e. the cell boundaries match exactly) and they are placed so that there is no overlap between them.
• The merge can be performed on any edge of either square.
• Each square can be rotated by \(90^\circ\), \(180^\circ\), \(270^\circ\), or \(360^\circ\) (i.e. no rotation) before merging. However, flipping (horizontal or vertical) is not allowed.

Your task is to determine the maximum area (i.e. the maximum number of soil cells) of any connected patch of soil that can be obtained by choosing the optimal rotations and merge edge between the two regions.

Note: When merged, the two regions will be adjacent but not overlapping. For example, if merging along the right edge of the first region, the second region should be placed so that its left edge is exactly to the right of the first region's right edge.

inputFormat

The first line contains an integer \(N\) representing the dimension of each square region. The next \(N\) lines describe the first region; each line contains \(N\) space-separated integers (either 0 or 1), where 1 represents soil and 0 represents rock. The following \(N\) lines describe the second region in the same format.

Example:

2
1 1
0 1
1 0
1 1

outputFormat

Output a single integer, the maximum area (number of soil cells) in any connected land component in the merged configuration when optimally rotated and aligned.

sample

1
1
1

2