#PQJ221x4101. QOJ 221_4101

    ID: 2780 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2016贪心

QOJ 221_4101

数字配对 【问题描述】 有n 种数字,第i 种数字是 ia 、有 ib 个,权值是 ic 。 若两个数字 ia 、 ja 满足, ia 是 ja 的倍数,且 j i a a 是一个质数,那么这两个数 字可以配对,并获得 j i c c  的价值。 一个数字只能参与一次配对,可以不参与配对。 在获得的价值总和不小于0 的前提下,求最多进行多少次配对。 【输入格式】 第一行一个整数n。 第二行n 个整数 1a 、 2 a 、……、 n a 。 第三行n 个整数 1b 、 2b 、……、 nb 。 第四行n 个整数 1c 、 2c 、……、 nc 。 【输出格式】 一行一个数,最多进行多少次配对。 【样例输入】 3 2 4 8 2 200 7 -1 -2 1 【样例输出】 4

【数据规模和约定】 测试点编号 n ia ib | | ic 1 ≤10 ≤10 9 1 ≤10 5 2 3 4 ≤200 ≤10 5 0 5 6 ≤10 5 7 8 9 10