#2031. 「SDOI2016」数字配对

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 11Dimensions

题目描述

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 \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