Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell 0.

There are also n cards, each card has 2 attributes: length li and cost ci. If she pays ci dollars then she can apply i-th card. After applying i-th card she becomes able to make jumps of length li, i. e. from cell x to cell (x - li) or cell (x + li).

She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible. 

If this is possible, calculate the minimal cost.

Input

The first line contains an integer n (1 ≤ n ≤ 300), number of cards.

The second line contains n numbers li (1 ≤ li ≤ 109), the jump lengths of cards.

The third line contains n numbers ci (1 ≤ ci ≤ 105), the costs of cards.

Output

If it is impossible to buy some cards and become able to jump to any cell, output -1. Otherwise output the minimal cost of buying such set of cards.

Examples

Input

3
100 99 9900
1 1 1


Output

2


Input

5
10 20 30 40 50
1 1 1 1 1


Output

-1


Input

7
15015 10010 6006 4290 2730 2310 1
1 1 1 1 1 1 10


Output

6


Input

8
4264 4921 6321 6984 2316 8432 6120 1026
4264 4921 6321 6984 2316 8432 6120 1026


Output

7237

Note

In first sample test, buying one card is not enough: for example, if you buy a card with length 100, you can't jump to any cell whose index is not a multiple of 100. The best way is to buy first and second card, that will make you be able to jump to any cell.

In the second sample test, even if you buy all cards, you can't jump to any cell whose index is not a multiple of 10, so you should output -1.
8
2 3 5 7 11 13 17 19
4 8 7 1 5 2 6 3
 1
2
2
 1
1000000000
100000
 1
1
1
 6
1 2 4 8 16 32
32 16 8 4 2 1
 2
1000000000 999999999
100000 100000
 39
692835 4849845 22610 1995 19019 114 6270 15 85085 27170 1365 1155 7410 238 3135 546 373065 715 110 969 15 10374 2730 19019 85 65 5187 26 3233230 1122 399 1122 53295 910 110 12597 16302 125970 67830
4197 6490 2652 99457 65400 96257 33631 23456 14319 22288 16179 74656 89713 31503 45895 31777 64534 27989 60861 69846 44586 87185 96589 62279 62478 6180 26977 12112 9975 72933 73239 65856 98253 18875 55266 55867 36397 40743 47977
 35
512 268435456 8 128 134217728 8192 33554432 33554432 536870912 512 65536 1048576 32768 512 524288 1024 536870912 536870912 16 32 33554432 134217728 2 16 16777216 8192 262144 65536 33554432 128 4096 2097152 33554432 2097152 2
36157 67877 79710 63062 12683 36255 61053 83828 93590 74236 5281 28143 7350 45953 96803 15998 11240 45207 63010 74076 85227 83498 68320 77288 48100 51373 87843 70054 28986 25365 98581 11195 43674 75769 22053

3
 -1 -1 1
 32
 200000
 18961
 -1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

/**
 * Created by yujiahao on 6/21/16.
 */
public class cf_290_d {
    private FastScanner in;
    private PrintWriter out;

    public void solve() throws IOException {
        int n = in.nextInt();
        int[] jump = new int[n];
        int[] costs = new int[n];
        for (int i=0; i<n; i++) jump[i] = in.nextInt();
        for (int i=0; i<n; i++) costs[i] = in.nextInt();

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i=0; i<n; i++){
            HashMap<Integer,Integer> next = new HashMap<Integer,Integer>();
            next.putAll(map);

            Iterator<Integer> ite = map.keySet().iterator();
            while (ite.hasNext()){
                int curr = ite.next();
                int cost = map.get(curr);
                curr = gcd(jump[i], curr);
                cost += costs[i];
                if (next.containsKey(curr)){
                    next.put(curr, Math.min(next.get(curr), cost));
                }else{
                    next.put(curr, cost);
                }
            }
            if (next.containsKey(jump[i])){
                next.put(jump[i], Math.min(costs[i], next.get(jump[i])));
            }else{
                next.put(jump[i], costs[i]);
            }
            map.clear();
            map.putAll(next);
        }

        if (map.containsKey(1)){
            out.print(map.get(1));
        }else{
            out.print("-1");
        }
        return;

    }

    int gcd(int a, int b){
        if (a<b)    return gcd(b,a);
        if (a%b==0) return b;
        return gcd(b, a%b);
    }

    public void run() {
        try {
            in = new FastScanner();
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() { return new BigInteger(next());}

    }

    public static void main(String[] arg) {
        new cf_290_d().run();
    }
}
