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.
#include <bits/stdc++.h>

using namespace std;

#define what_is(x) cerr << #x << " is " << x << endl;

const int INF = 1e9;

struct Network {
    vector<unordered_map<int, int>> residual_graph;
    vector<int> parent;
    vector<bool> seen;

    int num_nodes; //how many nodes are in the network

    Network(int n) {
        num_nodes = n;
        residual_graph.resize(num_nodes);
        parent.resize(num_nodes);
        seen.resize(num_nodes);
    }

    void add_edge(int u, int v, int c) {
        residual_graph[u][v] += c;
    }

    bool bfs(int s, int t) //check if augmenting path exists in the residual graph
    {
        queue<int> q;
        for (int i = 0; i < num_nodes; i++) {
            parent[i] = s;
            seen[i] = false;
        }
        while (!q.empty()) {
            q.pop();
        }

        q.push(s);
        seen[s] = true;
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            for (auto &[k, v] : residual_graph[curr]) {
                if (v > 0 && !seen[k]) //checks to see that the edge is not saturated and e.v has not been processed already
                {
                    parent[k] = curr;
                    seen[k] = true;
                    q.push(k);
                }
            }
        }
        return seen[t];
    }

    int maximum_flow(int s, int t) //runs ford-fulkerson to find the maximum flow between source s and sink t. assumes no cycles
    {
        int result = 0; //stores the maximum flow

        while (bfs(s, t)) {
            int minimum_residual_capacity = INF;
            for (int i = t; i != s; i = parent[i]) {
                minimum_residual_capacity = min(minimum_residual_capacity, residual_graph[parent[i]][i]);
            }
            result += minimum_residual_capacity;
            for (int i = t; i != s; i = parent[i]) {
                residual_graph[parent[i]][i] -= minimum_residual_capacity;
                residual_graph[i][parent[i]] += minimum_residual_capacity;
            }
            //cout << "minimum residual capacity: " << minimum_residual_capacity << "\n";
        }

        return result;
    }
};

void solve_test() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        sum += max(b[i], 0);
    }

    Network nw(n + 2);
    for(int i = 1; i <= n; i++) {
        if(b[i] > 0) {
            nw.add_edge(0, i, b[i]);
        }
        else {
            nw.add_edge(i, n + 1, -b[i]);
        }
    }

    vector<bool> seen(101);
    for (int i = 1; i <= n; i++) {
        for(int j = 1; j <= 100; j++) {
            seen[j] = false;
        }
        for(int j = i - 1; j >= 1; j--) {
            if(a[i] % a[j] == 0 && !seen[a[j]]) {
                seen[a[j]] = true;
                nw.add_edge(i, j, INF);
            }
        }

    }
    cout << sum - nw.maximum_flow(0, n + 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--) {
        solve_test();
    }
    return 0;
}
