Description

{{The rules are as follows:

LJC writes down two sequences of positive integers $A$ and $B$, both of length $N$. The two sequences are paired one-to-one, that is, for each $i$ there is a pair $(A_i, B_i)$.

Each time, HKE may choose an adjacent pair $A[i]$ and $A[i+1]$. If they are not coprime (i.e., $\gcd(A[i], A[i+1]) > 1$), he may remove this pair and gain $B[i] + B[i+1]$ points.

The removed pair is simultaneously deleted from both sequences, and the sequences are compacted (the remaining elements shift left).

When all adjacent pairs in the sequence are coprime, the game ends. HKE wants to know the maximum total score he can obtain.}}

Input Format

{{- Line 1: an integer $N$ (the length of the sequences).

• Line 2: $N$ integers, representing $A_1,$ $A_2, \ldots, A_N$.
• Line 3: $N$ integers, representing $B_1,$ $B_2, \ldots, B_N$.}}

Output Format

{{- Output one integer, the maximum total score HKE can obtain.}}

6
9 8 6 5 6 3
11 19 12 17 18 15

64
//解释：擦去A[2],A[3]与A[5],A[6]，得分为64

Hint

{{Sample Explanation:

• First remove $A[2]=8$ and $A[3]=6$, gaining $B[2]+B[3]=19+12=31$ points.
• After the update, they become $9, 5, 6, 3$ and $11, 17, 18, 15$.
• Then remove $A[3]=6$ and $A[4]=3$, gaining $B[3]+B[4]=18+15=33$ points.
• The total score is $31+33=64$.

Constraints:

• For 30% of the testdata, $N \leq 20$.
• For 60% of the testdata, $N \leq 100$.
• For 80% of the testdata, $N \leq 500$.
• For 100% of the testdata, $N \leq 800$.
• It is guaranteed that $1 \leq A_i, B_i \leq 10^9$.}}

Translated by ChatGPT 5