P4068 [SDOI2016] Number Pairing

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.

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 a single integer on one line: the maximum number of pairings.

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