[SDOI2016]数字配对

题目描述

有 n 种数字,第 i 种数字是 $a_i$、有 $b_i$ 个,权值是 $c_i$。 若两个数字 $a_i$、$a_j$ 满足,$a_i$ 是 $a_j$ 的倍数,且 $a_i/a_j$ 是一个质数, 那么这两个数字可以配对,并获得 $c_i \times c_j$ 的价值。 一个数字只能参与一次配对,可以不参与配对。 在获得的价值总和不小于 0 的前提下,求最多进行多少次配对。

输入输出格式

输入格式


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

输出格式


一行一个数,最多进行多少次配对

输入输出样例

输入样例 #1

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

输出样例 #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$ 。