Mamodos are mystical creatures with supernatural powers from the parallel Mamodo world. Every 1,000 years, one hundred Mamodo are transported to Earth to compete for the kingship of their world. Each Mamodo has a set of spells that requires a human companion to read aloud in order to cast them.
Now there is a competition between the mamodos. The rules are as follows. There's an infinite path of blocks indexed by integers (positive, negative and zero). Initially each mamodo has to stand at block 0. A spell of power p can make a mamodo jump from block b to block (b+p) or (b-p). The task is to be able to jump to any block (maybe by visiting some intermediate blocks).
Zatch is one of the good mamodos with Kiyo as his human companion. Now Kiyo has to buy the required spells for Zatch to win. Each spell has some cost c and Kiyo wants to spend as little money as possible. If it is impossible to buy some spells and become able to jump to any block print -1.
INPUT
The first line contains an integer n, number of spells.
The second line contains n numbers pi , the power of each spell .
The third line contains n numbers ci, the cost of spells.
CONTRAINTS
1<=n<=300
1<=pi<=10^9
1<=ci<=10^6
OUTPUT
Print the minimum cost of buying such set of spells.
PROBLEM AUTHOR
Vidushi Tripathi
In the sample test case, buying one spell is not enough. For example, if Kiyo buys a spell of power 2, he can only jump to blocks that are a multiple of 2. The best way is to buy first and second spell, which will make Zatch able to jump to any block.