Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:128 MB

#2926. 「SDOI2016」数字配对

统计

题目描述

有 $ 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$。

输出格式

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

样例

input

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

output

4

数据范围与提示

测试点 1 ~ 3:$ n \leq 10 $,$ a_i \leq 10 ^ 9 $,$ b_i = 1 $,$ \left| c_i \right| \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 $,$ \left| c_i \right| \leq 10 ^ 5 $。