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<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define maxn 3005
#define inf (1ll<<60)
using namespace std;
typedef long long ll;
ll n,a[maxn+5],b[maxn+5],lst[maxn+5],cur[maxn+5],d[maxn+5],s,t,sum,flow;
struct edge{
	ll v,w,id;
	edge(ll v=0,ll w=0,ll id=0):v(v),w(w),id(id){}
};
queue<ll> q;
vector<edge> adj[maxn+5];
inline void _read(ll &x){
	ll f=1;
	x=0;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')
			f=-1;
		else
			f=1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
	return;
}
inline void _print(ll x){
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>=10)
		_print(x/10);
	putchar(x%10+'0');
	return;
}
inline void addedge(ll u,ll v,ll w){
	adj[u].push_back(edge(v,w,adj[v].size()));
	adj[v].push_back(edge(u,0,adj[u].size()-1));
	return;
}
inline ll bfs(){
	while(!q.empty())
		q.pop();
	for(ll i=0;i<=maxn;i++)
		d[i]=-1;
	d[s]=0;
	q.push(s);
	ll u,v,w,id;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(ll i=0;i<adj[u].size();i++)
		{
			v=adj[u][i].v;
			w=adj[u][i].w;
			id=adj[u][i].id;
			if(w>0&&d[v]==-1)
			{
				d[v]=d[u]+1;
				if(v==t)
					return 1;
				q.push(v);
			}
		}
	}
	return 0;
}
inline ll dfs(ll u,ll f){
	if(u==t||f==0)
		return f;
	ll v,w,id,minflow,res=0;
	for(ll &i=cur[u];i<adj[u].size();i++)
	{
		v=adj[u][i].v;
		w=adj[u][i].w;
		id=adj[u][i].id;
		if(w<=0||d[v]!=d[u]+1)
			continue;
		minflow=dfs(v,min(w,f-res));
		res+=minflow;
		adj[u][i].w-=minflow;
		adj[v][id].w+=minflow;
		if(res==f)
			return res;
	}
	return res;
}
inline void dinic(){
	while(bfs())
	{
		for(ll i=0;i<=maxn;i++)
			cur[i]=0;
		flow+=dfs(s,inf);
	}
	return;
}
int main(){
	_read(n);
	for(ll i=1;i<=n;i++)
		_read(a[i]);
	for(ll i=1;i<=n;i++)
		_read(b[i]);
	s=0;
	t=n+1;
	for(ll i=1;i<=n;i++)
	{
		if(b[i]>0)
		{
			sum+=b[i];
			addedge(s,i,b[i]);
		}
		else
			addedge(i,t,-b[i]);
		for(ll j=1;j<=a[i];j++)
			if(a[i]%j==0&&lst[j])
				addedge(i,lst[j],inf);
		lst[a[i]]=i;
	}
	dinic();
	_print(sum-flow);
	return 0;
}
