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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e8;

int n, a[3010], b[3010];
int st, te;
int last[110];

struct Data
{ 
    int ver, fCur, fMax, id;

    Data() : ver(0), fCur(0), fMax(0), id(0) {}
    Data(int ver, int fCur, int fMax, int id) : ver(ver), fCur(fCur), fMax(fMax), id(id) {}
};
Data back[3010];
vector<Data> g[3010];

bool bfs()
{
    for (int i = 0; i < n; ++i)
        back[i].ver = -1;
    back[st].ver = st;

    queue<int> que;
    que.push(st);

    while (!que.empty())
    {
        int u = que.front();
        que.pop();

        if (u == te)
            return true;

        for (int i = 0; i < g[u].size(); ++i)
        {
            Data x = g[u][i];
            int v = x.ver;
            if (x.fCur == x.fMax || back[v].ver != -1)
                continue;
            
            que.push(v);
            back[v].ver = u;
            back[v].fCur = x.fCur;
            back[v].fMax = x.fMax;
            back[v].id = i;
        }
    }

    return false;
}

long long max_flow()
{
    long long ans = 0;
    while (bfs())
    {
        int tmp = te, f = INF;
        while (back[tmp].ver != tmp)
        {
            f = min(f, back[tmp].fMax - back[tmp].fCur);
            tmp = back[tmp].ver;
        }
        tmp = te;
        while (back[tmp].ver != tmp)
        {
            int u = back[tmp].ver, v = tmp, id;
            
            id = back[tmp].id;
            g[u][id].fCur += f;

            id = g[u][id].id;
            g[v][id].fCur -= f;

            tmp = back[tmp].ver;
        }
        
        ans += 1LL * f;
    }
    return ans;
}

void add_edge(int u, int v, int c)
{
    g[u].push_back(Data(v, 0, c, g[v].size()));
    g[v].push_back(Data(u, 0, 0, g[u].size() - 1));
}

int main()
{
    long long ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
    {
        cin >> b[i];
        ans += 1LL * max(0, b[i]);
    }

    st = n; te = n + 1;
    for (int i = 1; i <= 100; ++i)
        last[i] = -1;

    for (int i = 0; i < n; ++ i)
    {
        if (b[i] > 0)
            add_edge(st, i, b[i]);
        else
            add_edge(i, te, -b[i]);

        for (int j = 1; j <= 100; ++j)
            if (last[j] != -1 && a[i] % j == 0)
                add_edge(i, last[j], INF);
        
        last[a[i]] = i;
    }

    n += 2;
    ans -= max_flow();
    cout << ans;
}