Note that the memory limit is unusual.

You are given an integer n and two sequences a_1, a_2, ..., a_n and b_1, b_2, ..., b_n.

Let's call a set of integers S such that S ⊆ \{1, 2, 3, ..., n\} strange, if, for every element i of S, the following condition is met: for every j ∈ [1, i - 1], if a_j divides a_i, then j is also included in S. An empty set is always strange.

The cost of the set S is ∑_{i ∈ S} b_i. You have to calculate the maximum possible cost of a strange set.

Input

The first line contains one integer n (1 ≤ n ≤ 3000).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100).

The third line contains n integers b_1, b_2, ..., b_n (-10^5 ≤ b_i ≤ 10^5).

Output

Print one integer — the maximum cost of a strange set.

Examples

Input


9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1


Output


16


Input


2
42 42
-37 13


Output


0


Input


2
42 42
13 -37


Output


13

Note

The strange set with the maximum cost in the first example is \{1, 2, 4, 8, 9\}.

The strange set with the maximum cost in the second example is empty.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class CodeForces {
 
	public static void solve(FastReader sc, StringBuilder sb) {
 
		int n = sc.nextInt();
		int[] arr=sc.nextInts(n);
		int[] cost=sc.nextInts(n);
		int s=2*n+1,t=2*n+2;
		Flow flow=new Flow(2*n+2, s, t);
	
		
		for (int i = 1; i <= n; i++) {
			if (cost[i - 1] > 0)
				flow.addEdge(s, i, cost[i - 1]);
			else if (cost[i - 1] < 0)
				flow.addEdge(i, t, -cost[i - 1]);
		}
		long res = 0L;
		for (int i = 1; i <= n; i++) {
			boolean[] connected = new boolean[101];
			for (int j = i - 1; j >= 1; j--)
				if (arr[i - 1] % arr[j - 1] == 0 && !connected[arr[j - 1]]) {
					connected[arr[j - 1]] = true;
					flow.addEdge(i, j, Long.MAX_VALUE / 2);
				}
			res += Math.max(0, cost[i - 1]);
		}

		long cut = flow.getMinCut();
//		System.out.println(ans+" "+cut);
		System.out.println(res-cut);
		
//		for(int i=0;i<n;i++)
//			if(!map.containsKey(i)) System.out.println(i+" "+arr[i]+" "+cost[i]);
//			else System.out.println(i+" "+arr[i]+" "+cost[i]+" X");
//		sb.append(cut+" ");
	}
 
	
	public static void main(String[] args) throws FileNotFoundException {
		FastReader sc = new FastReader();
		StringBuilder sb = new StringBuilder();
		int t = 1;// sc.nextInt();
		while (t-- > 0) {
			solve(sc, sb);
		}
//		System.out.print(sb);
	}
 
}
class Flow{
	List<Edge>[] edges; 
	int src, sink,n;
	int[] level;

	Flow(int n,int src,int sink){
		this.n=n;
		this.src=src;
		this.sink=sink;
		edges=new ArrayList[n+1];
		for (int i = 0; i < edges.length; i++) {
			edges[i]=new ArrayList<>();
		}
		level=new int[n+1];
	}
	
	public void addEdge(int f,int to, long val) {
		Edge forward=new Edge(f, to, val);
		Edge backward=new Edge(to, f, 0L);
		forward.residual=backward;
		backward.residual=forward;
		edges[f].add(forward);
		edges[to].add(backward);
	}
	
	public long getMinCut() {
		long inf=Long.MAX_VALUE/2;
		long ans=0;
		while(bfs()) {
			int[] start = new int[n+1];
			long flow = dfs(src,inf,start);
//			System.out.println(flow);
			while(flow>0) {
				ans+=flow;
				flow=dfs(src,inf,start);
//				System.out.println(flow);
			}
		}
		return ans;
	}
 
	public long dfs(int curr, long flow, int[] start) {
		if(curr == sink)
            return flow;
        for(; start[curr] < edges[curr].size(); start[curr]++)
        {
            Edge e = edges[curr].get(start[curr]);
            if(e.capacityLeft() > 0 && level[e.to]-level[curr] == 1)
            {
                long val = dfs(e.to, Math.min(flow, e.capacityLeft()), start);
                if(val > 0)
                {
                    e.augment(val);
                    return val;
                }
            }
        }
        return 0L;  
	}

	public boolean bfs() {
		int def=-100;
		Arrays.fill(level, def);
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(src);
		level[src]=0;
		while(!q.isEmpty()) {
			int curr=q.remove();
			for(Edge ne:edges[curr]) {
				if(ne.capacityLeft()>0&&level[ne.to]==def) {
					q.add(ne.to);
					level[ne.to]=level[curr]+1;
				}
			}	
		}
		return level[sink]!=def;
	}
	
	class Edge{
		public int from, to;
        public long flow, capacity;
        public Edge residual;
 
        public Edge(int f, int t, long cap)
        {
            from = f;
            to = t;
            capacity = cap;
            flow=0;
        }
        public long capacityLeft()
        {
            return capacity-flow;
        }
        public void augment(long val)
        {
            flow += val;
            residual.flow -= val;
        }
	}
	
}

class FastReader {
	BufferedReader br;
	StringTokenizer st;

	public FastReader() throws FileNotFoundException {
		try{
			File file = new File("src\\input.txt");
			br = new BufferedReader(new FileReader(file));
		} catch(Exception e) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

	}

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

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

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

	double nextDouble() {
		return Double.parseDouble(next());
	}
	
	int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }
 
    long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }
    
    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }
    
	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}
}
