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.*;

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 1e9 + 10;
    static final long OO = (long) 2e18 + 10;
    static final int MOD = (int) 1e9 + 7;

    static class Dinic {
        class Edge {
            int v, rev, c, f;

            Edge(int v, int rev, int c) {
                this.v = v;
                this.rev = rev;
                this.c = c;
                f = 0;
            }
        }
        ArrayList<Edge>[] g;
        int[] layer, ptr;

        Dinic(int n) {
            g = new ArrayList[n];
            Arrays.setAll(g, i -> new ArrayList<>());
            layer = new int[n];
            ptr = new int[n];
        }

        void addEdge(int v, int u, int c) {
            g[v].add(new Edge(u, g[u].size(), c));
            g[u].add(new Edge(v, g[v].size() - 1, 0));
        }

        boolean bfs(int s, int t) {
            Arrays.fill(layer, -1);
            layer[s] = 0;
            LinkedList<Integer> q = new LinkedList<>();
            q.add(s);
            while (!q.isEmpty()) {
                int v = q.poll();
                for (Edge e : g[v]) {
                    if (e.f < e.c && layer[e.v] == -1) {
                        layer[e.v] = layer[v] + 1;
                        q.add(e.v);
                    }
                }
            }
            return layer[t] != -1;
        }

        int dfs(int v, int t, int delta) {
            if (v == t)
                return delta;
            for (; ptr[v] < g[v].size(); ptr[v]++) {
                Edge e = g[v].get(ptr[v]);
                if (e.f < e.c && layer[e.v] == layer[v] + 1) {
                    int pushed = dfs(e.v, t, Math.min(delta, e.c - e.f));
                    if (pushed > 0) {
                        e.f += pushed;
                        g[e.v].get(e.rev).f -= pushed;
                        return pushed;
                    }
                }
            }
            return 0;
        }

        int maxFlow(int s, int t) {
            int flow = 0;
            while (bfs(s, t)) {
                Arrays.fill(ptr, 0);
                int delta;
                while ((delta = dfs(s, t, oo)) > 0)
                    flow += delta;
            }
            return flow;
        }
    }

    static void solve() {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = in.nextInt();
        }

        Dinic dinic = new Dinic(n + 2);
        int s = n, t = n + 1;
        int[] last = new int[101];
        Arrays.fill(last, -1);
        for (int i = 0; i < n; i++) {
            if (b[i] >= 0)
                dinic.addEdge(s, i, b[i]);
            else
                dinic.addEdge(i, t, -b[i]);
            for (int j = 1; j <= a[i]; j++) {
                if (a[i] % j == 0 && last[j] != -1)
                    dinic.addEdge(i, last[j], oo);
            }
            last[a[i]] = i;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (b[i] > 0)
                sum += b[i];
        }

        out.println(sum - dinic.maxFlow(s, t));

    }

    public static void main(String[] args) {
        in = new FastReader();
        out = new PrintWriter(System.out);

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            this(System.in);
        }
        FastReader(String file) throws FileNotFoundException {
            this(new FileInputStream(file));
        }
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }
        String nextLine() {
            String line;
            try {
                line = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
    }
}