跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0153. #2031. 「SDOI2016」数字配对

  • ID: 159
  • 传统题
  • 1000ms
  • 128MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 数论
  • 数学
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2031. 「SDOI2016」数字配对

题目描述

有 种数字,第 种数字是 、有 个,权值是 。
若两个数字 、 满足, 是 的倍数,且 是一个质数,那么这两个数字可以配对,并获得 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于 的前提下,求最多进行多少次配对。

输入格式

第一行一个整数 。
第二行 个整数 a1,a2,…,an。
第三行 个整数 b1,b2,…,bn。
第四行 个整数 c1,c2,…,cn。

输出格式

一行一个整数,表示最多进行多少次配对。

样例

样例输入

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

样例输出

4

数据范围与提示

测试点 1 ~ 3:,,,;
测试点 4 ~ 5:,,,;
测试点 6 ~ 10:,,,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 36 题。保留原作者与原赛事署名。