题目描述

森林可以抽象为一个 $n\times n$ 的矩阵，每个元素描述一棵树的高度。

Mirko 为每棵树测量了它们一年生长的米数。注意：如果一棵树一年长 $5$ 米，半年就会长 $2.5$ 米。

Mirko 想知道，若已知森林里所有树木的当前高度及生长速度，如果这些树继续以它们当时生长的速度生长，那么所有高度相同的连成一组的树的的树的棵数最大会是多少。

两棵树或一组树是相邻的条件如下：

• 如果两棵树在矩阵中共享一条公共边，则它们是相邻的。
• 如果有从第一棵树到第二棵树的相邻树序列，则两棵树是相邻的。
• 如果组中的每对树都是相邻的，则一组树是相邻的。

输入格式

第一行仅一个整数 $n$。

接下来 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个数指 $h_{i,j}$，表示第 $i$ 行第 $j$ 列中树的初始高度，以米为单位。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数指 $v_{i,j}$，表示第 $i$ 行第 $j$ 列中树的生长速度，以米为单位。

由于输入量较大，请使用更快的输入方法。

输出格式

仅一行一个整数，即为题中所求。

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

提示

样例 2 说明

$8$ 个月后，位于 $(0,0),(0,1),(1,0)$ 的树木高度将达到 $\dfrac{13}{3}$ 米，这 $3$ 棵树是相邻的一组树，所以应该输出 3。

数据规模与约定

• 对于 $30\%$ 的数据。有 $1\le n\le 70$。
• 对于 $100\%$ 的数据，有 $1\le n\le 700$。

对于所有合法的 $h_{i,j}$ 和 $v_{i,j}$，都有 $1\le h_{i,j},v_{i,j}\le 10^6$。

说明

题目译自 COCI2014-2015 CONTEST #2 T5 ŠUMA。