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>
 
//define
#define trav(i,v)   for(auto i: v)
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define all(v)  v.begin(), v.end()
#define itn int 
    
//typedef
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
// const long long MOD = 1000000007;
const long long MOD = 998244353;
const long long inf = 1000000000000000000;
const long long small_inf = 100000000000000;
 
using namespace std;

ll modpow(ll x, ll n, ll mod = MOD){ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%MOD; n>>=1;} return res;} 
ll power(ll x, ll n){ll res=1; while(n>0){ if(n&1) res=res*x; x=x*x; n>>=1;} return res;}

template<typename T>
struct dinic {
    struct edge{
        int n, rev;
        T flow, cap;
        edge(int n, int rev, T flow, T cap):n(n), rev(rev), flow(flow), cap(cap) {}
    };
    vector<vector<edge>> v;
    T flow, scaling_lim;
    vector<int> lev, pos;
    int n, s, t;
    bool scaling;
    dinic(int n, int s, int t, bool scaling):n(n), flow(0), s(s), t(t), scaling(scaling)
    {
        v.resize(n);
        lev.resize(n);
        pos.resize(n);
        fill(all(lev),-1);
    }
    void add_edge(int x, int y, T cap, bool directed = true)
    {
        v[x].pb(edge(y,(int)v[y].size(),0,cap));
        v[y].pb(edge(x,(int)v[x].size()-1,0,directed == true? 0: cap));
        return;
    }
    bool bfs()
    {
        queue<int> q;
        q.push(s);
        lev[s] = 0;
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            if(x==t)
                return true;
            trav(u,v[x])
            {
                if(lev[u.n]!=-1 || u.cap - u.flow < scaling_lim)
                    continue;
                lev[u.n] = lev[x] + 1;
                q.push(u.n);
            }
        }
        return false;
    }
    T dfs(int x, T f)
    {
        if(x==t)
            return f;
        if(f==0)
            return f;
        T res = 0;
        for(; pos[x] < (int)v[x].size(); pos[x]++)
        {
            auto& u = v[x][pos[x]];
            if(lev[u.n]-lev[x]!=1)
                continue;
            T new_f = dfs(u.n, min(f, u.cap - u.flow));
            if(new_f>0)
            {
                u.flow += new_f;
                v[u.n][u.rev].flow -= new_f;
                f -= new_f;
                res += new_f;
            }
            if(f==0)
                break;
        }
        return res;
    }
    T calc()
    {
        flow = 0;
        rep(i,n)
            trav(u,v[i])
                u.flow = 0;
        scaling_lim = scaling == true? numeric_limits<T>::max() / 2 + 1: 1; 
        for( ; scaling_lim > 0; scaling_lim = scaling_lim>>1)
        {
            // cout<<scaling_lim<<" ";
            while(1)
            {
                fill(all(lev),-1);
                if(bfs())
                {
                    fill(all(pos),0);
                    T ans;
                    while(ans = dfs(s, numeric_limits<T>::max()))
                    {
                        flow += ans;
                    }
                }
                else
                {
                    fill(all(lev),-1);
                    break;
                }
            }
        }
        return flow;
    }
    vector<bool> min_cut()
    {
        vector<bool> v1(n,1);
        rep(i,n)
            if(lev[i]!=-1)
                v1[i] = 0;
        return v1;
    }
};

void init()
{
    
}

void solve()
{
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    // INITIALIZE USING dinic<int/ll(depending on size of flow/cut)> d(num of nodes, start, sink, scaling(false for ford-fulkerson))
    // ADD EDGE USING d.add_edge(i,j,cap) => edge i to j of capacity cap
    // CALCULATE MAX FLOW USING ll max_flow = d.calc()
    // FIND MIN CUT USING vector<bool> v = d.min_cut()
    // EXAMPLE ->
    // dinic<ll> d(n + 2, s, t, true); -> for dinic algorithm
    // dinic<ll> d(n + 2, s, t, false); -> for ford fulkerson
    // d.add_edge(i, j, cap);
    // ll max_flow = d.calc();
    // vector<bool> v = d.min_cut();

    int t23 = 1, tt23=1;
    // cin>>t23;    
    init();
    while(tt23<=t23)
    {
        // cout<<"Case #"<<tt23<<": ";
        solve();
        tt23++;
    }
    int n;
    cin >> n;
    vector<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];
    int s = n;
    int t = n + 1;
    dinic<ll> d(n + 2, s, t, true);
    vector<int> last(101, -1);
    for(int i = 0; i < n; i++){
        if(b[i] > 0)
            d.add_edge(s, i, b[i]);
        if(b[i] < 0)
            d.add_edge(i, t, -b[i]);
        for(int k = 1; k <= 100; k++)
            if(last[k] != -1 && a[i] % k == 0)
            {
                d.add_edge(i, last[k], 1e11);
            }
        last[a[i]] = i;    
    }   
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += max(0, b[i]);
    cout << sum - d.calc() << endl;
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}