题目描述

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

输入格式

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

输出格式

一行一个数，最多进行多少次配对

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

4

提示

n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5

题目来源

鸣谢Menci上传