#P4514. [Sdoi2016]数字配对

    ID: 3751 传统题 1000ms 128MiB 尝试: 2699 已通过: 744 难度: 8 上传者: 标签>难度分类提高+/省选-数论试除法分解质因数图论二分图建模构造与建模奇偶性分析势能优化费用流Dijkstra残量增广路CF2400费用流

[Sdoi2016]数字配对

[SDOI 2016] 数字配对

题目描述

有 nn 种数字。第 ii 种数字的值为 aia_i,共有 bib_i 个,每个的权值为 cic_i。

如果 aia_i 是 aja_j 的倍数,且 aiaj\dfrac{a_i}{a_j} 是质数,就可以从第 ii 种、第 jj 种数字中各取一个配成一对,获得价值 cicjc_i c_j。每个数字最多参加一次配对,也可以不参加配对。

在所有配对的价值总和不小于 00 的前提下,求最多能配成多少对。

输入格式

第一行输入一个整数 nn。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行输入 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

第四行输入 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

输出一行一个整数,表示最多能配成的对数。

样例

3
2 4 8
2 200 7
-1 -2 1
4

数据规模与约定

1≤n≤2001\le n\le200,1≤ai≤1091\le a_i\le10^9,0≤bi≤1050\le b_i\le10^5,∣ci∣≤105\lvert c_i\rvert\le10^5。

原赛测试点 nn 上界 aia_i 上界 bib_i 条件 ∣ci∣\lvert c_i\rvert 上界
1–3 1010 10910^9 bi=1b_i=1 10510^5
4–5 200200 bi≤105b_i\le10^5 00
6–10 10510^5