Maximum Score Game

This problem involves two sequences A and B each of length N. The elements in these sequences are paired by their positions. A game is played as follows:

• In each move, you may choose an adjacent pair in A, say A[i] and A[i+1], provided that they are not coprime (i.e. \(\gcd(A[i], A[i+1]) \neq 1\)).
• If you remove the pair A[i] and A[i+1], you gain a score equal to \(B[i] + B[i+1]\). Simultaneously, the corresponding elements in sequence B are also removed and the remaining parts of both sequences are concatenated in order (i.e. reindexed).
• The game ends when every adjacent pair in sequence A is coprime, meaning no further moves can be made.

Your task is to compute the maximum possible score that can be obtained by performing these moves in an optimal order.

Note: The greatest common divisor is denoted by \(\gcd(a, b)\).

inputFormat

The first line contains an integer N indicating the length of the sequences.

The second line contains N integers representing the sequence A.

The third line contains N integers representing the sequence B.

outputFormat

Output a single integer, the maximum score that can be obtained.

sample

2
2 3
4 5

0