题目背景

Problem	Score	Idea	Std	Data	Check	Solution
\(\text{D - Dreamed Sequence}\)	\(425\)	orchardist	orchardist	joe_zxq	fcy20180201	Link by joe_zxq

题目描述

给定长度为 \(N\) 的序列 \(A\) 和 \(B\)。

定义 \(A\) 和 \(B\) 两序列相乘 \(A\times B\) 的规则如下，其中模数 \(M=10^9+7\)：

• 设 \(A\) 序列为 \(\{A_1,A_2,\dots,A_N\}\)，\(B\) 序列为 \(\{B_1,B_2,\dots,B_N\}\)，则相乘得到的序列为 \(\{A_1B_1 \bmod M,A_2B_2 \bmod M,\dots,A_NB_N \bmod M\}\)。

数学家小 G 梦想着让 \(A\times B\) 得到的序列中出现次数最多的数出现的次数尽可能大。为了实现这一点，小 G 可以将 \(B\) 数组任意重排列。小 G 想知道，出现次数最多的数最多出现多少次。

请你帮小 G 找到他梦想中的序列。如果小 G 获得了诺贝尔数学奖，他将会与你分享奖金。

输入格式

第一行包含一个整数 \(N\)。

第二行包含 \(N\) 个整数，表示 \(A\) 序列。

第三行包含 \(N\) 个整数，表示 \(B\) 序列。

输出格式

一个整数，表示答案。

输入输出样例 #1

输入 #1

5
1 2 3 4 5
2 4 6 8 5

输出 #1

3

输入输出样例 #2

输入 #2

10
1 12 38 48 10 19 23 19 32 6
10 46 20 11 36 25 36 28 50 50

输出 #2

3

输入输出样例 #3

输入 #3

2
1 999999999
1 1000000000

输出 #3

1

说明/提示

样例解释 #1

重排 \(B\) 序列得 \(\{8,4,5,2,6\}\)，此时 \(A\times B\) 得到的数组为 \(\{8,8,15,8,30\}\)，其中 \(8\) 出现次数最多，出现 \(3\) 次。

可以证明不存在重排 \(B\) 序列的方式，使得答案大于 \(3\)。

数据范围

对于 \(100\%\) 的数据，保证 \(1 \le N \le 2000\)，\(1 \le A_i,B_i \le 10^9\)。