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 NN 6100
#define MM 1000100

using namespace std;
using INT=long long;
using pii = pair<int, int>;

const int inf=0x3f3f3f3f;

int V, E, src, tar;
int head[NN], work[NN], dis[NN];
int to[MM], cap[MM], nxt[MM];
int q[NN], qf, qb;

void init(int n, int s, int t){
	V=n; E=0; src=s; tar=t;
	memset(head, -1, sizeof(int)*V);
}

void add_edge(int u, int v, int c){
	to[E]=v; cap[E]=c; nxt[E]=head[u]; head[u]=E++;
	to[E]=u; cap[E]=0; nxt[E]=head[v]; head[v]=E++;
}

bool bfs(){
	memset(dis, -1, sizeof(int)*V);
	qf=qb=0;
	q[qb++]=src; dis[src]=0;
	while(qf<qb && dis[tar]==-1){
		int u=q[qf++];
		for(int i=head[u]; i>=0; i=nxt[i]){
			int v=to[i];
			if(dis[v]==-1 && cap[i]>0){
				dis[v]=dis[u]+1;
				q[qb++]=v;
			}
		}
	}
	return dis[tar]>=0;
}

int dfs(int u, int &bot){
	int v, bot1, delta;
	if(u==tar) return bot;
	for(int &i=work[u]; i>=0; i=nxt[i]){
		int v=to[i];
		if(dis[v]!=dis[u]+1 || cap[i]==0) continue;
		bot1=min(bot, cap[i]);
		if(delta=dfs(v, bot1)){
			cap[i]-=delta;
			cap[i^1]+=delta;
			bot=bot1;
			return delta;
		}
	}
	return 0;
}

int dinic(){
	int ans=0, delta, bot;
	while(bfs()){
		memcpy(work, head, sizeof(int)*V);
		delta=inf;
		while(delta=dfs(src, bot=inf)) ans+=delta;
	}
	return ans;
}

const int N = 100010;

int a[NN], b[NN], vst[NN];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
	int sr = 0, tar = n + 1;
	
	init(2 * n + 10, sr, tar);
	
	for(int i = 1; i <= n; i ++) {
		add_edge(sr, i, N);
		add_edge(i, tar, N - b[i]);
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= 100; j ++) vst[j] = 0;
		for(int j = i - 1; j >= 1; j --) {
			if(a[i] % a[j] == 0) {
				int ok = 0;
				for(int k = a[j]; k <= 100; k += a[j]) {
					if(vst[k]) {
						ok = 1;
						break;
					}
				}
				if(!ok) add_edge(i, j, inf);
				vst[a[j]] = 1;
			}
		}
	}
	int ans = dinic();
	ans -= N * n;
	ans = - ans;
	cout << ans << endl;
	
}
            