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

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

n n n 种数字,第 i i i 种数字是 ai a_i ai、有 bi b_i bi 个,权值是 ci c_i ci
若两个数字 ai a_i aiaj a_j aj 满足,ai a_i aiaj a_j aj 的倍数,且 ai/aj a_i / a_j ai/aj 是一个质数,那么这两个数字可以配对,并获得 ci⋅cj c_i \cdot c_j cicj 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于 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 n10ai≤109 a_i \leq 10 ^ 9 ai109bi=1 b_i = 1 bi=1∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ci105
测试点 4 ~ 5:n≤200 n \leq 200 n200ai≤109 a_i \leq 10 ^ 9 ai109bi≤105 b_i \leq 10 ^ 5 bi105ci=0 c_i = 0 ci=0
测试点 6 ~ 10:n≤200 n \leq 200 n200ai≤109 a_i \leq 10 ^ 9 ai109bi≤105 b_i \leq 10 ^ 5 bi105∣ci∣≤105 \left| c_i \right| \leq 10 ^ 5 ci105