10429: #2031. 「SDOI2016」数字配对

有 $n$ 种数字，第 $i$ 种数字是 ai a_i a​i​​、有 bi b_i b​i​​ 个，权值是 ci c_i c​i​​。
若两个数字 ai a_i a​i​​、aj a_j a​j​​ 满足，ai a_i a​i​​ 是 aj a_j a​j​​ 的倍数，且 ai/aj a_i / a_j a​i​​/a​j​​ 是一个质数，那么这两个数字可以配对，并获得 ci⋅cj c_i \cdot c_j c​i​​⋅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\le 10$，ai≤109 a_i \leq 10 ^ 9 a​i​​≤10​9​​，bi=1 b_i = 1 b​i​​=1，∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ∣c​i​​∣≤10​5​​；
测试点 4 ~ 5：$n\le 200$，ai≤109 a_i \leq 10 ^ 9 a​i​​≤10​9​​，bi≤105 b_i \leq 10 ^ 5 b​i​​≤10​5​​，ci=0 c_i = 0 c​i​​=0；
测试点 6 ~ 10：$n\le 200$，ai≤109 a_i \leq 10 ^ 9 a​i​​≤10​9​​，bi≤105 b_i \leq 10 ^ 5 b​i​​≤10​5​​，∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ∣c​i​​∣≤10​5​​。