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 int long long
// #define double long double
// #define endl "\n"
const int MAXN = 3e3 + 7;
const int MAXE = 1e5 + 7;
// const int MOD = ;
const int INF = 0x3f3f3f3f;
// const double eps = ;
// const double PI = acos(-1);
// const int DIRX[] = {};
// const int DIRY[] = {};

struct Dicnic
{
    // Dicnic Algorithm
    // Find Max Flow in nonnegative Graph
    // Time Complexity: O(V^2E)
    // Edge add twice for Reverse Edge
    struct Edge
    {
        int to;
        int val;
        int nxt;
    }edge[MAXE * 2];

    int cntEdge;
    int head[MAXN];

    void init()
    {
        cntEdge = -1; // edge 0 ^ 1 = reverse edge 1
        memset(head, -1, sizeof(head));
    }

    void addEdge(int u, int v, int w)
    {
        ++cntEdge;
        edge[cntEdge].to = v;
        edge[cntEdge].val = w;
        edge[cntEdge].nxt = head[u];
        head[u] = cntEdge;
    }

    int dep[MAXN]; // depth in BFS 
    int arc[MAXN]; // arc optimization

    bool bfs(int s, int t)
    {
        memset(dep, 0, sizeof(dep));
        queue<int> q;
        dep[s] = 1;
        arc[s] = head[s];
        q.push(s);
        while (!q.empty())
        {
            int now = q.front(); q.pop();
            for (int i = head[now]; ~i; i = edge[i].nxt)
            {
                int to = edge[i].to;
                if (dep[to] == 0 && edge[i].val > 0)
                {
                    dep[to] = dep[now] + 1;
                    arc[to] = head[to];
                    q.push(to);
                    if (to == t)
                        return true;
                }
            }
        }
        return false;
    }

    int dfs(int now, int flow, int t)
    {
        if (now == t)
            return flow;
        int res = 0;
        for (int i = arc[now]; (~i) && flow; i = edge[i].nxt)
        {
            arc[now] = i;
            int to = edge[i].to;
            if (edge[i].val && dep[to] == dep[now] + 1)
            {
                int nxtFlow = dfs(to, min(flow, edge[i].val), t);
                if (nxtFlow == 0)
                    dep[to] = 0;
                edge[i].val -= nxtFlow;
                edge[i ^ 1].val += nxtFlow;
                flow -= nxtFlow;
                res += nxtFlow;
            }
        }
        return res;
    }

    int dicnic(int s, int t)
    {
        int ans = 0;
        while (bfs(s, t))
            ans += dfs(s, INF, t);
        return ans;
    }
}dic;

int n;
int a[MAXN];
bool vis[100 + 7];
int ans;

int32_t main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    dic.init();
    ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        memset(vis, false, sizeof(vis));
        for (int j = i - 1; j; --j)
        {
            if (a[i] % a[j] == 0 && vis[a[j]] == false)
            {
                dic.addEdge(i, j, INF);
                dic.addEdge(j, i, 0);
                vis[a[j]] = true;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        int val;
        cin >> val;
        if (val > 0)
        {
            dic.addEdge(0, i, val);
            dic.addEdge(i, 0, 0);
            ans += val;
        }
        else
        {
            dic.addEdge(i, n + 1, -val);
            dic.addEdge(n + 1, i, 0);
        }
    }
    ans -= dic.dicnic(0, n + 1);
    cout << ans << endl;
    return 0;
}