Alice 和璀璨花

题目信息

时间限制: 1s

空间限制: 256M

输入文件: alice.in

输出文件: alice.out

题目描述

著名的植物学家 Alice 经过多年的探索，终于找到了传说中的璀璨花。璀璨花的生长速度非常迅猛，如果不加以合适的控制，璀璨花会因为过度内耗而死亡。璀璨花的生长趋势可以用序列 $a$ 表示，Alice 在研读前人对璀璨花的研究后总结出了一个控制序列 $b$。Alice 需要让璀璨花的生长趋势尽可能贴合控制序列，这样璀璨花就能尽可能快且安全地生长，以让更多人能欣赏到传说花卉的美。

Alice 可以通过基因编辑技术让 $a$ 的任意子序列 $a'$ 成为璀璨花的生长趋势，设 $a'$ 的长度为 $n'$，若 $\forall i \in[1, n'-1] \cap \mathbb{N}, a'_{i+1}>b_i a'_i$，那么璀璨花的培育趋势就是安全的。另外，越长的生长趋势能让成熟的璀璨花更美，所以 Alice 想知道可能的最长的璀璨花生长趋势子序列的长度。

输入格式

第一行一个整数 $N$，表示数列的长度。

第二行 $N$ 个数表示序列 $a$。

第三行 $N$ 个数表示序列 $b$。

输出格式

一个整数，表示最长的璀璨花生长趋势子序列的长度。

样例

样例输入1

4
1 2 3 10
2 3 4 5

样例输出1

3

样例解释1

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

数据范围与提示

• 对于测试点 1-5，$N\leq 100$
• 对于测试点 6-10，$N\leq 1000$
• 对于测试点 11，$b_i=i+1$
• 对于测试点 12-13，$b_i > 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$