5013 - [COCI 2014-2015 #2] ŠUMA

树木是森林的一部分,树木生长迅速。森林可以抽象为一个 n\times n 的矩阵,每个区域包含一棵树。

Mirko 非常喜欢魔法森林里的树。他花了数年的时间观察它们,并为每棵树测量它们一年生长多少米。也就是说,如果这棵树一年长 5 米,半年就会长 2.5 米。

除了树木,Mirko 还喜欢魔法森林里的蘑菇。有时,他吃着可疑的五颜六色的蘑菇,开始思考一些奇怪的问题。他想知道,如果这些树继续以它们当时生长的速度生长,那么所有高度相同的连成一组的树的的树的棵数最大会是多少。

Mirko 迅速测量了森林里所有树木的当前高度,并让你回答他的问题。

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

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

输入

第一行输入包含整数 n

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

接下来 n 行,每行 n 个整数。第 i 行包含整数 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

提示

【样例二说明】

8 个月后(\dfrac{2}{3} 年),位于 (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

时间限制 3 秒
内存限制 256 MB
讨论 统计
上一题 下一题