[SDOI 2016] 数字配对
题目描述
有 n 种数字。第 i 种数字的值为 ai,共有 bi 个,每个的权值为 ci。
如果 ai 是 aj 的倍数,且 ajai 是质数,就可以从第 i 种、第 j 种数字中各取一个配成一对,获得价值 cicj。每个数字最多参加一次配对,也可以不参加配对。
在所有配对的价值总和不小于 0 的前提下,求最多能配成多少对。
输入格式
第一行输入一个整数 n。
第二行输入 n 个整数 a1,a2,…,an。
第三行输入 n 个整数 b1,b2,…,bn。
第四行输入 n 个整数 c1,c2,…,cn。
输出格式
输出一行一个整数,表示最多能配成的对数。
样例
3
2 4 8
2 200 7
-1 -2 1
4
数据规模与约定
1≤n≤200,1≤ai≤109,0≤bi≤105,∣ci∣≤105。
| 原赛测试点 |
n 上界 |
ai 上界 |
bi 条件 |
∣ci∣ 上界 |
| 1–3 |
10 |
109 |
bi=1 |
105 |
| 4–5 |
200 |
bi≤105 |
0 |
| 6–10 |
105 |