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 lowbit(x) ((x)&(-(x)))
#define mkp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MAXN=3e3+10;
const int MAXM=2e6+10;
const int inf=1e9;

struct Edge
{
	int to,nxt,w;	
};

int n,S,T,cnt_e=1;
int a[MAXN],b[MAXN];
int head[MAXN],cur_h[MAXN];
int deep[MAXN];
Edge e[MAXM];

inline void addedge(int u,int v,int w)
{
	e[++cnt_e].to=v;
	e[cnt_e].w=w;
	e[cnt_e].nxt=head[u];
	head[u]=cnt_e;
}

inline bool bfs()
{
	for(int i=1;i<=n+2;i++) cur_h[i]=head[i];
	for(int i=1;i<=n+2;i++) deep[i]=-1;
	queue<int> q; 
	q.push(S); deep[S]=1;
	
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to,w=e[i].w;
			if(deep[v]!=-1 || !w) continue;
			
			deep[v]=deep[u]+1;
			q.push(v);
			if(v==T) return true;
		}
	}
	return false;
}

inline int dfs(int u,int flow)
{
	if(u==T || !flow) return flow;
	int res=0;
	for(int &i=cur_h[u];i;i=e[i].nxt)
	{
		int v=e[i].to,w=e[i].w;
		if(deep[v]!=deep[u]+1 || !w) continue;
		
		int k=dfs(v,min(flow,w));
		if(!k) deep[v]=-1;
		
		e[i].w-=k; e[i^1].w+=k;
		flow-=k; res+=k;
		if(!flow) break;
	}
	return res;
}

inline int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(S,inf);
	return res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    
    S=n+1; T=n+2;
    int sum=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		if(b[i]>0)
		{
			sum+=b[i];
			addedge(S,i,b[i]);
			addedge(i,S,0);
		}
		else
		{
			addedge(i,T,-b[i]);
			addedge(T,i,0);
		}
	}
	
	static int lst[110];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=100;j++)
			if(a[i]%j==0 && lst[j])
			{
				addedge(i,lst[j],inf);
				addedge(lst[j],i,0);
			}
		lst[a[i]]=i;
	}
	
	printf("%d\n",sum-dinic());
    return 0;
}

