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;

const int maxn = 3030;

const int inf = 1e9;

struct edge {
    int from, to, cap, flow;
};

int s,t,tot;
vector<edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];

void init() {
    edges.clear();
    for (int i = 0; i <= t; i++)G[i].clear();
}

void addedge(int from,int to,int cap) {
    edges.push_back(edge{from, to, cap, 0});
    edges.push_back(edge{to, from, 0, 0});
    tot = edges.size();
    G[from].push_back(tot - 2);
    G[to].push_back(tot - 1);
}

bool bfs() {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < G[x].size(); i++) {
            edge &e = edges[G[x][i]];
            if (!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                q.push(e.to);
            }
        }
    }
    return vis[t];
}

int dfs(int x,int a) {
    if (x == t || a == 0)return a;
    int flow = 0, f;
    for (int &i = cur[x]; i < G[x].size(); i++) {
        edge &e = edges[G[x][i]];
        if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if (a == 0)break;
        }
    }
    return flow;
}


int maxflow() {
    int flow = 0;
    while (bfs()) {
        memset(cur, 0, sizeof(cur));
        flow += dfs(s, inf);
    }
    return flow;
}

int n;
int a[maxn], b[maxn];
int pos[maxn];

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    s = 0, t = n + 1;
    int res = 0;
    for (int i = 1; i <= n; ++i){
        cin >> b[i];
        if(b[i] > 0) {
            addedge(s, i, b[i]);
            res += b[i];
        }
        else addedge(i, t, -b[i]);
    }

    for (int i = 1; i <= n; ++i){
        memset(pos, -1, sizeof(pos));
        for (int j = 1; j < i; ++j){
            if(a[i] % a[j] == 0) pos[a[j]] = j;
        }
        for(int j = 0; j <= 100; j++){
            if(pos[j] != -1) {
                addedge(i, pos[j], inf);
            }
        }
    }
    cout << res - maxflow() << "\n";
    return 0;
}
