Description

A forest can be modeled as an $n \times n$ matrix, where each element describes the height of a tree.

Mirko measured how many meters each tree grows in one year. Note: if a tree grows $5$ meters in one year, then it grows $2.5$ meters in half a year.

Mirko wants to know: given the current height and growth rate of every tree in the forest, if these trees continue to grow at their current rates, what is the maximum possible number of trees in a connected group whose heights are all equal.

Two trees, or a group of trees, are considered connected as follows:

• If two trees share a common edge in the matrix, then they are adjacent.
• If there is a sequence of adjacent trees from the first tree to the second tree, then the two trees are connected.
• If every pair of trees in the group is connected, then the group of trees is connected.

Input Format

The first line contains a single integer $n$.

The next $n$ lines each contain $n$ integers. The number in row $i$ and column $j$ is $h_{i,j}$, representing the initial height of the tree at position $(i, j)$, in meters.

The next $n$ lines each contain $n$ integers. The number in row $i$ and column $j$ is $v_{i,j}$, representing the growth rate of the tree at position $(i, j)$, in meters.

Because the input is large, please use a faster input method.

Output Format

Output a single line containing one integer, which is the answer.

3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

7

2
3 1
3 3
2 5
2 5

3

Hint

Explanation of Sample 2

After $8$ months, the heights of the trees at $(0,0), (0,1), (1,0)$ will become $\dfrac{13}{3}$ meters. These $3$ trees form a connected group, so the output should be 3.

Constraints

• For $30\%$ of the testdata, $1 \le n \le 70$.
• For $100\%$ of the testdata, $1 \le n \le 700$.

For all valid $h_{i,j}$ and $v_{i,j}$, $1 \le h_{i,j}, v_{i,j} \le 10^6$.

Note

This problem is translated from COCI2014-2015 CONTEST #2 T5 ŠUMA.

Translated by ChatGPT 5