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;


mt19937 rnd(time(0));
#define ios ios_base::sync_with_stdio(false);cin.tie(0);
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define smin(x, y) x = min(x, y)
#define smax(x, y) x = max(x, y)
#define pii pair<int,int>
#define int long long
#define ld long double
#define pld pair<ld,ld>


const int N = 53;
const int inf = 1e9;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const int MAXN = 3e9;

struct edge {
    int v, u, c, f, inv;

    edge(int v, int u, int c, int inv) : v(v), u(u), c(c), f(0), inv(inv) {}
};

int n, s, t;

vector<edge> edgeList;
vector<vector<int>> g;
vector<int> ptr;

void addEdge(int v, int u, int c) {
    g[v].pb(edgeList.size());
    edgeList.pb({v, u, c, 0});
    g[u].pb(edgeList.size());
    edgeList.pb({u, v, 0, 1});
}


//int fordFulkersonScaling() {
//    int maxLim = (1ll << 32);
//
//    int maxFlow = 0;
//    for (int scalingLimit = maxLim; scalingLimit > 0; scalingLimit /= 2) {
//
//        while (true) {
//            used.assign(n + 2, false);
//            int push = dfs(s, inf, scalingLimit);
//            if (!push)break;
//            maxFlow += push;
//        }
//    }
//
//    return maxFlow;
//}

vector<int> d;

int dfs(int v, int flow, int limit) {
    if (v == t)return flow;

    for (;ptr[v] < (int)g[v].size(); ++ptr[v]) {
        int id = g[v][ptr[v]];
        int u = edgeList[id].u;
        if (edgeList[id].c - edgeList[id].f < limit || d[u] != d[v] + 1)continue;
        int delta = dfs(u, min(flow, edgeList[id].c - edgeList[id].f), limit);
        if (delta) {
            edgeList[id].f += delta;
            edgeList[id ^ 1].f -= delta;
            return delta;
        }
    }

    return 0;
}


bool bfs(int scalingLim) {
    d.assign(n + 2, -1);
    d[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int id : g[v]) {
            int u = edgeList[id].u;
            if (edgeList[id].c - edgeList[id].f >= scalingLim && d[u] == -1) {
                d[u] = d[v] + 1;
                q.push(u);
            }
        }
    }

    return d[t] != -1;
}

//int dinic() {
//    int maxFlow = 0;
//
//    while (bfs()) {
//        while (int push = dfs(s, inf, 1))maxFlow += push;
//    }
//
//    return maxFlow;
//}

int dinicScaling() {
    int maxFlow = 0;

    for (int scalingLim = (1ll << 32); scalingLim > 0; scalingLim >>= 1) {
        while (bfs(scalingLim)) {
            ptr.assign(n + 2, 0);
            while (int push = dfs(s, inf, scalingLim))maxFlow += push;
        }
    }
    return maxFlow;
}

signed main() {
    ios;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; ++i)cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<int> prev(101, -1);
    g.resize(n + 2);

    s = n;
    t = n + 1;

    for (int i = 0; i < n; ++i) {
        for (int d = 1; d <= 100; ++d) {
            if (prev[d] != -1 && a[i] % d == 0)addEdge(i, prev[d], inf);
        }
        prev[a[i]] = i;

        if (b[i] > 0) {
            addEdge(s, i, b[i]);
        } else if (b[i] < 0) {
            addEdge(i, t, -b[i]);
        }
    }

    int minCut = dinicScaling();
    int sum = 0;
    for (int i : b)sum += max(0ll, i);

    cout << sum - minCut;
}