题目描述

给你一个长度为 $n$ 的序列 $a = \{ a_1, a_2, \ldots, a_n \}$，和一个长度为 $n$ 的序列 $b = \{ b_1, b_2, \ldots, b_n \}$。

你需要找到序列 $a$ 的一个最长的子序列，不妨设这个子序列为 $a' = \{ a'_1, a'_2, \ldots, a'_m \}$，这个序列需要满足以下条件：

• 对于任意 $1 \le i \lt m$，均有 $b_i \times a'_i \lt a'_{i+1}$。

你需要输出满足条件的最长的子序列长度（即上面描述中的 $m$）。

输入格式

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

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

第三行，$n$ 个整数 $b_1, b_2, \ldots, b_n$，以空格分隔。

输出格式

输出一个整数，表示满足条件的最长子序列 $a'$ 的长度。

样例

4
1 2 3 10
2 3 4 5

3

10
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1

10

说明/提示

样例 1 解释

$\{ 1, 3, 10 \}$ 是 $a$ 的一个子序列，满足 $2 \times 1 \lt 3$，$3 \times 3 \lt 10$

数据规模与约定

• 对于测试点 1-5，$N \leq 100$
• 对于测试点 6-10，$N \leq 1000$
• 对于测试点 11，$b_i=i+1$
• 对于测试点 12-13，$b_i \gt 1$
• 对于测试点 14-16，$b_i = 1$
• 对于测试点 17-20，没有特殊限制
• 对于所有数据，$N \leq 10^6, 1 \leq a_i \leq 10^{12}, 1 \leq b_i \leq 10^6$