题目描述

有$n$种数字，第$i$种数字是$a_i$、有$b_i$个，权值是$c_i$。

若两个数字$a_i$、$a_j$满足，$a_i$是$a_j$的倍数，且$a_i / a_j$是一个质数，那么这两个数字可以配对，并获得$c_i \cdot c_j$的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于$0$的前提下，求最多进行多少次配对。

输入格式

第一行一个整数$n$。
第二行$n$个整数$a_1, a_2, \dots, a_n$。
第三行$n$个整数$b_1, b_2, \dots, b_n$。
第四行$n$个整数$c_1, c_2, \dots, c_n$。

输出格式

一行一个整数，表示最多进行多少次配对。

样例

输入

3
2 4 8
2 200 7
-1 -2 1

输出

4

数据范围与提示

• 测试点 1 ~ 3：$n \leq 10$，$a_i \leq 10^9$，$b_i = 1$，$|c_i| \leq 10^5$；
• 测试点 4 ~ 5：$n \leq 200$，$a_i \leq 10^9$，$b_i \leq 10^5$，$c_i = 0$；
• 测试点 6 ~ 10：$n \leq 200$，$a_i \leq 10^9$，$b_i \leq 10^5$，$|c_i| \leq 10^5$。