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

//package CodeForce;
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
/**
 *
 * @author prabhat
 */
public class P797B {
    

   static int[] a;
   static long[] sum;
   static int mod=1000000007;
   static int[][] dp;
   static boolean[][] isPalin;
   static int max1=5000+10;
   static int[][] g;
   static int ver;
   static int t,n,k,m,x;
   static boolean[] visit,isprime;
   static LinkedList<Pair> l[];
   static int ans=0,max_len=8;
   static int[] color,log,st[],lpf;
   static String[] S;static TreeSet<Point> ts;
   static LinkedList<Pair> adj[];
   static InputReader in;
   static PrintWriter pw;
   static  Point[] point;static char[] s;
   static String[] node;
   static long[] grundy={0,1,2,2,3,3,0,0,0,0,0,0};
  public static void main(String[] args) throws Exception
   {
   	 in = new InputReader(System.in);
       // BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
     //Scanner sc=new Scanner();
   	pw=new PrintWriter(System.out);
        n=in.ii();
        int[]l=in.iia(n);
        int[] c=in.iia(n);
       /// int cost=0;
              HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for(int i=0;i<n;i++){
			HashMap<Integer,Integer> next = new HashMap<Integer,Integer>();
			next.putAll(map);
			
			Iterator<Integer> it = map.keySet().iterator();
			while(it.hasNext()){
				int curr = it.next();
				int cost = map.get(curr);
				curr = gcd(curr,l[i]);
				cost += c[i];
				if(next.containsKey(curr))
					next.put(curr, Math.min(next.get(curr), cost));
				else
					next.put(curr, cost);
			}
			
			if(next.containsKey(l[i]))
				next.put(l[i], Math.min(next.get(l[i]),c[i]));
			else
				next.put(l[i], c[i]);
			
			map.clear();
			map.putAll(next);
		}
		
        if(map.containsKey(1))
            pw.println(map.get(1));
        else pw.println(-1);
        pw.close();
   }
 
    static class Pair implements Comparable<Pair>
    {

        int x,i;
        long y;

        public Pair(int x, long y) {
            this.x = x;
            this.y = y;
        }
        
        Pair (int x, int y,int i)
        {
		this.x = x;
                this.y = y;
                this.i = i;
	}
	
	public int compareTo(Pair o) {
                return Long.compare(this.y,o.y);
	}

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 

  static boolean isvalid(int i,int j)
  {
      if(i>=0&&i<n&&j>=0&&j<m)return true;
      return false;
  }
  static double dist(double x1,double y1,double x2,double y2)
  {
    double ans=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    return (Math.ceil(Math.sqrt(ans)));
  }

  
 static long gcd1(long a,long b)
 {
  long res=1L;
  while(a>0)
  {
     res=a;
     a=b%a;
     b=res;
  }
  return res;
 }
public static double calculateAngle(double x1, double y1, double x2, double y2)
{
    double angle = Math.toDegrees(Math.atan2(x2 - x1, y2 - y1));
    // Keep angle between 0 and 360
    angle = angle + Math.ceil( -angle / 360 ) * 360;

    return angle;
}
static void seive()
{
    isprime=new boolean[1000005];
    Arrays.fill(isprime, true);
    isprime[0]=false;
    isprime[1]=false;
    lpf=new int[1000005];
    for(int i=1;i<=1000000;i++)lpf[i]=i;
   
    for(int i=2;i<=1000;i++)
    {
      if(lpf[i]!=i)continue;
      int j=i+i;
      while(j<=1000000)
      {
        lpf[j]=i;
        j+=i;
      }
      
    }
  
}
  static BigInteger power(BigInteger x, BigInteger y, BigInteger m)
			{
			    if (y.equals(new BigInteger("0")))
			        return (new BigInteger("1"));
			    BigInteger p = power(x, y.divide(new BigInteger("2")), m).mod(m);
			    p = (p.multiply(p)).mod(m);

			    return (y.mod(new BigInteger("2")).equals(new BigInteger("0")))? p : (p.multiply(x)).mod(m);
		        }

  static char[][] trans(char[][] s)
  {
    int n=s.length;
    int m=s[0].length;
   char[][] trans=new char[m][n];
    for(int i=0;i<m;i++)
    {
     for(int j=0;j<n;j++)
     {
       trans[i][j]=s[j][i];
     }
    }
  return trans;
  }
  public static String toBase26(int n)
  {
		StringBuffer ret = new StringBuffer();
		while(n>0)
                {
			--n;
			ret.append((char)('A' + n%26));
			n/=26;
		}
		return ret.reverse().toString();
	}
 
 static void log()
 {
   log[1]=0;
   for(int i=2;i<=n;i++)
   {
    log[i]=log[i/2]+1;
   }
 }

  private static class DSU{
		int[] parent;
		int[] rank;
		int cnt;
		public DSU(int n){
			parent=new int[n];
			rank=new int[n];
			for(int i=0;i<n;i++){
				parent[i]=i;
				rank[i]=1;
			}
			cnt=n;
		}
		int find(int i){
	        while(parent[i] !=i){
	        	parent[i]=parent[parent[i]];
	        	i=parent[i];
	        }
	        return i;
	    }
		int Union(int x, int y){
	        int xset = find(x);
	        int yset = find(y);
	        if(xset!=yset)
	        	cnt--;
	        if(rank[xset]<rank[yset]){
	        	parent[xset] = yset;
		        rank[yset]+=rank[xset];
		        rank[xset]=0;
		        return yset;
	        }else{
	        	parent[yset]=xset;
	        	rank[xset]+=rank[yset];
	        	rank[yset]=0;
	        	return xset;
	        }
	    }
	}
  public static int[][] packU(int n, int[] from, int[] to, int max) {
	    
	    int[][] g = new int[n][];
	    int[] p = new int[n];
	    for (int i = 0; i < max; i++) p[from[i]]++;
	    for (int i = 0; i < max; i++) p[to[i]]++;
	    for (int i = 0; i < n; i++) g[i] = new int[p[i]];
	    for (int i = 0; i < max; i++) {
	        g[from[i]][--p[from[i]]] = to[i];
	        g[to[i]][--p[to[i]]] = from[i];
	    }
	    return g;
	}
	public static int[][] parents3(int[][] g, int root) {
	    int n = g.length;
	    int[] par = new int[n];
	    Arrays.fill(par, -1);
 
	    int[] depth = new int[n];
	    depth[0] = 0;
 
	    int[] q = new int[n];
	    q[0] = root;
	    for (int p = 0, r = 1; p < r; p++) {
	        int cur = q[p];
	        for (int nex : g[cur]) {
	            if (par[cur] != nex) {
	                q[r++] = nex;
	                par[nex] = cur;
	                depth[nex] = depth[cur] + 1;
	            }
	        }
	    }
	    return new int[][]{par, q, depth};
	}
	public static int lower_bound(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
        return nums[low] == target ? low : -1;
    }
 
    public static int upper_bound(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high + 1 - low) / 2;
            if (nums[mid] > target)
                high = mid - 1;
            else
                low = mid;
        }
        return nums[low] == target ? low : -1;
    }
  public static boolean palin(String s)
	{
	   int i=0;
	   int j=s.length()-1;
	   while(i<j)
	   {
		   if(s.charAt(i)==s.charAt(j))
		   {
			   i++;
			   j--;
		   }
		   else return false;     
	   }
	   return true;
	}
	
    static boolean CountPs(String s,int n)
       {
    	boolean b=false;
    	     char[] S=s.toCharArray();
	       int[][] dp=new int[n][n];
	       boolean[][] p=new boolean[n][n];
	       for(int i=0;i<n;i++)p[i][i]=true;
	     
	       for(int i=0;i<n-1;i++)
	       {
	    	   if(S[i]==S[i+1])
	    	   {
	    		p[i][i+1]=true;
	    		dp[i][i+1]=1;
	    		b=true;
	    	   }
	       }
	    
	       for(int gap=2;gap<n;gap++)
	       {
	    	   for(int i=0;i<n-gap;i++)
	    	   {
	    		   int j=gap+i;
	    		   if(S[i]==S[j]&&p[i+1][j-1]){p[i][j]=true;}
	    		  
	    		  if(p[i][j])
	    			   dp[i][j]=dp[i][j-1]+dp[i+1][j]+1-dp[i+1][j-1];
	    		   
	    		   else  dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1];
	    		  
	    		   if(dp[i][j]>=1){b=true;}
	    	   }
	       }
	      
	    return b; 
   // return dp[0][n-1];
	       
    }
  
  
  
 
 
public static int gcd(int a,int b)
{
	int res=1;
	while(a>0)
	{
		res=a;
		a=b%a;
		b=res;
	}
	return res;
}
 
 
public static long pow(long n,long p,long m)
{
	 long  result = 1;
	  if(p==0)
	    return 1;
	if (p==1)
	    return n;
	while(p!=0)
	{
	    if(p%2==1)
	        result *= n;
	    if(result>=m)
	    result%=m;
	    p >>=1;
	    n*=n;
	    if(n>=m)
	    n%=m;
	}
	return result;
}
public static long pow(long n,long p)
{
	long  result = 1;
	  if(p==0)
	    return 1;
	if (p==1)
	    return n;
	while(p!=0)
	{
	    if(p%2==1)
	        result *= n;
	    p >>=1;
	    n*=n;
	}
	return result;
 
}
 
 
 
 
static class Edge implements Comparator<Edge> {
	public int u;
	public int v;
	public int w;
	public Edge() {
	}
	public Edge(int u, int v, int w) {
		this.u=u;
		this.v=v;
		this.w=w;
	}
	public int getU() {
		return u;
	}
	public void setU(int u) {
		this.u = u;
	}
	public int getV() {
		return v;
	}
	public void setV(int v) {
		this.v = v;
	}
	public int getW() {
		return w;
	}
	public void setW(int w) {
		this.w = w;
	      }
	
	@Override
	public int compare(Edge e1, Edge e2) {
		return  e2.w-e1.w;
	}
}
 
 
 

static  class InputReader
{
   private InputStream stream;
   private byte[] buf = new byte[1024];
 
   private SpaceCharFilter filter;
    byte inbuffer[] = new byte[1024];
   int lenbuffer = 0, ptrbuffer = 0;
    final int M = (int) 1e9 + 7;
   int md=(int)(1e7+1);
    int[] SMP=new int[md];
   final double eps = 1e-6;
   final double pi = Math.PI;
 
	PrintWriter out;
   String check = "";
 InputStream   obj = check.isEmpty() ? System.in : new ByteArrayInputStream(check.getBytes());
   public InputReader(InputStream stream)
   {
       this.stream = stream;
   }
 
    int readByte() {
	        if (lenbuffer == -1) throw new InputMismatchException();
	        if (ptrbuffer >= lenbuffer) {
	            ptrbuffer = 0;
	            try {
	                lenbuffer = obj.read(inbuffer);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	        }
	        if (lenbuffer <= 0) return -1;
	        return inbuffer[ptrbuffer++];
   }
 
   public  int read()
   {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       int sgn = 1;
       if (c == '-')
       {
           sgn = -1;
           c = read();
       }
       int res = 0;
       do
       {
           if (c < '0' || c > '9')
               throw new InputMismatchException();
           res *= 10;
           res += c - '0';
           c = read();
       } while (!isSpaceChar(c));
       return res * sgn;
   }
 
   String is() {
	        int b = skip();
	        StringBuilder sb = new StringBuilder();
	        while (!(isSpaceChar(b))) // when nextLine, (isSpaceChar(b) && b!=' ')
	        {
	            sb.appendCodePoint(b);
	            b = readByte();
	        }
	        return sb.toString();
   }
   public   int ii() {
	        int num = 0, b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }
 public   long il() {
	        long num = 0;
	        int b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }
   
	    boolean isSpaceChar(int c) {
	        return (!(c >= 33 && c <= 126));
	       }
 
	      int skip()
	        {
	        int b;
	        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
	        return b;
	        }
 
	    float nf() {
	        return Float.parseFloat(is());
	    }
 
	    double id() {
	        return Double.parseDouble(is());
	    }
 
	    char ic() {
	        return (char) skip();
	    }
 
	    int[] iia(int n) {
	        int a[] = new int[n];
	        for (int i = 0; i<n; i++) a[i] = ii();
	        return a;
	    }
 
	    long[] ila(int n) {
	        long a[] = new long[n];
	        for (int i = 0; i <n; i++) a[i] = il();
	        return a;
	    }
 
	    String[] isa(int n) {
	        String a[] = new String[n];
	        for (int i = 0; i < n; i++) a[i] = is();
	        return a;
	    }
 
 
		 long mul(long a, long b) { return a * b % M; }
 
			long div(long a, long b)
				 {
					return mul(a, pow(b, M - 2));
 
		           }
 
 
 
	    double[][] idm(int n, int m) {
	        double a[][] = new double[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = id();
	        return a;
	        }
 
	    int[][] iim(int n, int m) {
	        int a[][] = new int[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j <m; j++) a[i][j] = ii();
	        return a;
          }
 
 
   public String readLine() {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       StringBuilder res = new StringBuilder();
       do {
           res.appendCodePoint(c);
           c = read();
       } while (!isEndOfLine(c));
       return res.toString();
   }
 
   public interface SpaceCharFilter
   {
       public boolean isSpaceChar(int ch);
   }
   public boolean isEndOfLine(int c) {
       return c == '\n' || c == '\r' || c == -1;
   }
}
 
}
 