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 | $\le 10$ | $\le 10^9$ | $1$ | $\le 10^5$ | ||
| 2 | ||||||
| 3 | ||||||
| 4 | $\le 200$ | $\le 10^5$ | $0$ | |||
| 5 | ||||||
| 6 | ||||||
| 7 | ||||||
| 8 | ||||||
| 9 | $\le 10^5$ | |||||
| 10 |
Examples
Input 1
3 2 4 8 2 200 7 -1 -2 1
Output 1
4