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 long long
#define ull unsigned long long
#define pii pair<int, int>
#define mii map<int, int>
#define pb push_back
#define mk make_pair
const int inf = 0x3f3f3f3f;
const ll mod = 1000000007;
const ll linf = 0x3f3f3f3f3f3f3f3f;
#define deb(k) cerr << #k << ": " << k << "\n";
#define fastcin cin.tie(0)->sync_with_stdio(0);
#define st first
#define nd second
#define MAXN 3010
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = numeric_limits<ll>::max();
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;
	}

	void clear() {
		for( int n = 0 ; n < MAXN ; ++n ) adj[n].clear();
	}

	bool inCut( int u ){ return dist[u] != -1; }

};

max_flow g;
int last[110];
int a[3010];
int b[3010];

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	int sour = 0, sink = n+1;
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(b[i] >= 0){
			g.add(sour, i, b[i]);
		}
		else{
			g.add(i, sink, abs(b[i]));
		}
		for(int j=1;j<=a[i];j++){
			if(a[i]%j == 0 && last[j]) g.add(i, last[j], inf);
		}
		ans += max(0, b[i]);
		last[a[i]] = i;
	}
	cout<<ans - g.calc(sour, sink)<<"\n";


	// Have you read the problem again?
	// Maybe you understood the wrong problem
}

int main(){
	fastcin;
	solve();
	return 0;
}
