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 ll int
#define pb push_back
#define MAXN 3005
#define INF 0x3f3f3f3f

class max_flow {
	struct edge {
		int t;
		unsigned long rev;
		ll cap, f;
	};
	vector<edge> adj[MAXN];
	int dist[MAXN];
	int ptr[MAXN];
	bool bfs( int s, int t ) {
		memset( dist, -1, sizeof dist );
		dist[s] = 0;
		queue<int> q( { s } );
		while( !q.empty() && dist[t] == -1 ) {
			int n = q.front();
			q.pop();
			for( edge& e : adj[n] ) {
				if( dist[e.t] == -1 && e.cap != e.f ) {
					dist[e.t] = dist[n] + 1;
					q.push( e.t );
				}
			}
		}
		return dist[t] != -1;
	}

	ll aug( int n, ll amt, int t ) {
		if( n == t ) return amt;
		for( ; ptr[n] < adj[n].size() ; ++ptr[n] ) {
			edge& e = adj[n][ptr[n]];
			if( dist[e.t] == dist[n] + 1 && e.cap != e.f ) {
				ll flow = aug( e.t, min( amt, e.cap - e.f ), t );
				if( flow != 0 ) {
					e.f += flow;
					adj[e.t][e.rev].f -= flow;
					return flow;
				}
			}
		}
		return 0;
	}

public:
	void add( int u, int v, ll cap=1, ll rcap=0 ) {
		adj[u].push_back({ v, adj[v].size(), cap, 0 });
		adj[v].push_back({ u, adj[u].size() - 1, rcap, 0 });
	}

	ll calc( int s, int t ) {
		ll flow = 0;
		while( bfs( s, t ) ) {
			memset( ptr, 0, sizeof ptr );
			while( ll df = aug( s, INF, t ) ) flow += df;
		}
		return flow;
	}
};

max_flow g;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin >> n;
    int s = n, t = n+1;
    vector<int> ult(MAXN, -1), 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 resp = 0;
    for( int i = 0 ; i < n ; ++i ){
        if( b[i] >= 0 ) {
            resp += b[i];
            g.add(s, i, b[i]);
            for( int x = 1 ; x < MAXN ; ++x )
                if( a[i]%x == 0 and ult[x] != -1 )
                    g.add(i, ult[x], INF);
        }else{
            g.add(i, t, -b[i]);
            if( ult[a[i]] != -1 ) g.add(i, ult[a[i]], INF);
            ult[a[i]] = i;
        }
    }
    cout << resp - g.calc(s, t) << "\n";
    return 0;
}
