#2031. 「SDOI2016」数字配对
题目描述
有 n n n 种数字，第 i i i 种数字是 ai a_i ai、有 bi b_i bi 个，权值是 ci c_i ci。
若两个数字 ai a_i ai、aj a_j aj 满足，ai a_i ai 是 aj a_j aj 的倍数，且 ai/aj a_i / a_j ai/aj 是一个质数，那么这两个数字可以配对，并获得 ci⋅cj c_i \cdot c_j ci⋅cj 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 0 0 的前提下，求最多进行多少次配对。
输入格式
第一行一个整数 nnn。
第二行 nnn 个整数 a1,a2,…,an。
第三行 nnn 个整数 b1,b2,…,bn。
第四行 nnn 个整数 c1,c2,…,cn。
输出格式
一行一个整数，表示最多进行多少次配对。
样例
样例输入
3
2 4 8
2 200 7
-1 -2 1样例输出
4数据范围与提示
测试点 1 ~ 3：n≤10 n \leq 10 n≤10，ai≤109 a_i \leq 10 ^ 9 ai≤109，bi=1 b_i = 1 bi=1，∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ∣ci∣≤105；
测试点 4 ~ 5：n≤200 n \leq 200 n≤200，ai≤109 a_i \leq 10 ^ 9 ai≤109，bi≤105 b_i \leq 10 ^ 5 bi≤105，ci=0 c_i = 0 ci=0；
测试点 6 ~ 10：n≤200 n \leq 200 n≤200，ai≤109 a_i \leq 10 ^ 9 ai≤109，bi≤105 b_i \leq 10 ^ 5 bi≤105，∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ∣ci∣≤105。