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 fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
const int N=3005;
const int M=N*2*15;
const int inf=0x3f3f3f3f;
int n,S,T,a[N],b[N],las[N],sum;
int et=1,hed[N];
struct edge{int nx,to,fl;}e[M];
void addedge(int u,int v,int fl){e[++et].nx=hed[u],e[et].to=v,e[et].fl=fl,hed[u]=et;}
void adde(int u,int v,int fl){addedge(u,v,fl),addedge(v,u,0);}
int dep[N],cur[N];
bool bfs(){
	queue<int>q;
	rep(i,1,T)dep[i]=0,cur[i]=hed[i];
	q.push(S),dep[S]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=hed[u];i;i=e[i].nx){
			int v=e[i].to;
			if(e[i].fl&&!dep[v]){
				dep[v]=dep[u]+1,q.push(v);
				if(v==T)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int fl){
	if(u==T)return fl;
	int rl=0,used=0;
	for(int i=cur[u];i;i=e[i].nx){
		int v=e[i].to;cur[u]=i;
		if(e[i].fl&&dep[v]==dep[u]+1){
			rl=dfs(v,min(e[i].fl,fl-used));
			if(rl)e[i].fl-=rl,e[i^1].fl+=rl,used+=rl;
			if(used==fl)return used;
		}
	}
	return used;
}
signed main(){
	n=read(),S=n+1,T=S+1;
	rep(i,1,n)a[i]=read();
	rep(i,1,n)b[i]=read();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=a[i];++j)if(a[i]%j==0&&las[j])adde(i,las[j],inf);
		las[a[i]]=i;
		if(b[i]>0)sum+=b[i],adde(S,i,b[i]);
		else adde(i,T,-b[i]);
	}
	while(bfs())sum-=dfs(S,inf);
	cout<<sum<<'\n';
}