There are $n$ types of numbers. The $i$-th type of number is $a_i$, there are $b_i$ of them, and each has a weight $c_i$.
If two numbers $a_i$ and $a_j$ satisfy the condition that $a_i$ is a multiple of $a_j$ and $\frac{a_i}{a_j}$ is a prime number, then these two numbers can be paired, yielding a value of $c_i \cdot c_j$.
Each individual number can participate in at most one pairing, and it is allowed for a number not to participate in any pairing.
Given that the total value obtained must be no less than $0$, find the maximum number of pairings that can be performed.
Input
The first line contains an integer $n$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$.
The third line contains $n$ integers $b_1, b_2, \dots, b_n$.
The fourth line contains $n$ integers $c_1, c_2, \dots, c_n$.
Output
A single line containing one integer, the maximum number of pairings.
Data Scale and Conventions
| Test Case ID | $n$ | $a_i$ | $b_i$ | $ | c_i | $ |
|---|---|---|---|---|---|---|
| 1 | .h=3 $\le 10$ | .h=10 $\le 10^9$ | .h=3 $1$ | .h=3 $\le 10^5$ | ||
| 2 | ||||||
| 3 | ||||||
| 4 | .h=7 $\le 200$ | .h=7 $\le 10^5$ | .h=2 $0$ | |||
| 5 | ||||||
| 6 | .h=5 $\le 10^5$ | |||||
| 7 | ||||||
| 8 | ||||||
| 9 | ||||||
| 10 |
Examples
Input 1
3 2 4 8 2 200 7 -1 -2 1
Output 1
4