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.*;
import java.util.*;

public class prac {
	public static void main(String args[]) throws Exception {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int[] a = sc.nextInts(N);
		int[] cost = sc.nextInts(N);
		int source = 2 * N + 1;
		int sink = 2 * N + 2;
		MF flow = new MF(2 * N + 2, source, sink);
		for (int i = 1; i <= N; i++) {
			if (cost[i - 1] > 0)
				flow.addEdge(source, i, cost[i - 1]);
			else if (cost[i - 1] < 0)
				flow.addEdge(i, sink, -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 (a[i - 1] % a[j - 1] == 0 && !connected[a[j - 1]]) {
					connected[a[j - 1]] = true;
					flow.addEdge(i, j, Long.MAX_VALUE / 2);
				}
			res += Math.max(0, cost[i - 1]);
		}
		System.out.println(res - flow.minCut());
	}
}

class MF {
	public int N, src, target;
	public ArrayList<Edge>[] edges;
	private int[] level;

	public MF(int n, int x, int y) {
		N = n;
		src = x;
		target = y;
		edges = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			edges[i] = new ArrayList<Edge>();
		level = new int[N + 1];
	}

	public void addEdge(int from, int to, long cap) {
		Edge forward = new Edge(from, to, cap);
		Edge backward = new Edge(to, from, 0L);
		forward.residual = backward;
		backward.residual = forward;
		edges[from].add(forward);
		edges[to].add(backward);
	}

	public long minCut() {
		long res = 0L;
		int[] start = new int[N + 1];
		while (bfs()) {
			long flow = dfs(src, Long.MAX_VALUE / 2, start);
			while (flow > 0) {
				res += flow;
				flow = dfs(src, Long.MAX_VALUE / 2, start);
			}
			start = new int[N + 1];
		}
		return res;
	}

	private boolean bfs() {
		Arrays.fill(level, -69);
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.add(src);
		level[src] = 0;
		while (q.size() > 0) {
			int curr = q.poll();
			for (Edge e : edges[curr])
				if (e.capacityLeft() > 0 && level[e.to] == -69) {
					level[e.to] = level[curr] + 1;
					q.add(e.to);
				}
		}
		return level[target] != -69;
	}

	private long dfs(int curr, long flow, int[] start) {
		if (curr == target)
			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; // no flow
	}

	private 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;
		}

		public long capacityLeft() {
			return capacity - flow;
		}

		public void augment(long val) {
			flow += val;
			residual.flow -= val;
		}
	}
}

class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;
 
    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }
 
    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }
 
    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }
 
    public int nextInt() {
        return (int) nextLong();
    }
 
    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }
 
    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }
 
    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }
 
    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }
 
    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }
 
    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}