Description

There are $n$ types of numbers. For the $i$-th type, the number is $a_i$, there are $b_i$ copies of it, and its weight is $c_i$.

If two numbers $a_i$ and $a_j$ satisfy that $a_i$ is a multiple of $a_j$, and $a_i / a_j$ is a prime number, then these two numbers can be paired, gaining a value of $c_i \times c_j$.

Each number can participate in at most one pairing, and it is allowed to remain unpaired.

Under the condition that the total gained value is at least $0$, find the maximum possible number of pairings.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$.

The third line contains $n$ integers $b_1,b_2,\cdots,b_n$.

The fourth line contains $n$ integers $c_1,c_2,\cdots,c_n$.

Output Format

Output a single integer on one line: the maximum number of pairings.

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

4

Hint

Test points $1 \sim 3$: $n \leq 10$, $a_i \leq 10^9$, $b_i = 1$, $|c_i| \leq 10^5$.
Test points $4 \sim 5$: $n \leq 200$, $a_i \leq 10^9$, $b_i \leq 10^5$, $c_i = 0$.
Test points $6 \sim 10$: $n \leq 200$, $a_i \leq 10^9$, $b_i \leq 10^5$, $|c_i| \leq 10^5$.

Translated by ChatGPT 5