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<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N=20005;
const int M=300005;
const int inf=0x3f3f3f3f;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct edge{
	int to,next;
	long long cost;
}g[M*2];
int head[N],d[N],cnt=1,now[N],a[N],b[N],u[105];
queue<int> q;
void add(int u,int v,int w){
	g[++cnt].to=v;g[cnt].next=head[u];head[u]=cnt;g[cnt].cost=w;
	g[++cnt].to=u;g[cnt].next=head[v];head[v]=cnt;g[cnt].cost=0;
}
bool bfs(int s,int t){
	memset(d,0,sizeof(d));
	while(q.size()) q.pop();
	q.push(s);d[s]=1;now[s]=head[s];
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=g[i].next){
			if(g[i].cost&&!d[g[i].to]){
				q.push(g[i].to);
				now[g[i].to]=head[g[i].to];
				d[g[i].to]=d[x]+1;
				if(g[i].to==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int t,int flow){
	if(x==t) return flow;
	long long minn=flow,k;
	for(int i=now[x];i&&minn;i=g[i].next){
		now[x]=i;
		if(g[i].cost&&d[g[i].to]==d[x]+1){
			k=dinic(g[i].to,t,min(minn,g[i].cost));
			if(!k) {d[g[i].to]=0;continue;} 
			g[i].cost-=k;
			g[i^1].cost+=k;
			minn-=k;
			if(!g[i].cost) break; 
		}
	}
	return flow-minn;
}
long long solve(int s,int t){
	long long ans=0,flow=0;
	while(bfs(s,t)){
		while(flow=dinic(s,t,inf)) ans+=flow;
	}
	return ans;
}
int main()
{
	//freopen("test.in","r",stdin); 
	int n;
	long long sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
	    scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++) {
	    scanf("%d",&b[i]);
	    if(b[i]>0) sum+=b[i];
	}
	for(int i=1;i<=n;i++){
		memset(u,0,sizeof(u));
		for(int j=i+1;j<=n;j++){
			if(a[j]%a[i]==0&&!u[a[j]]) u[a[j]]=1,add(j,i,inf);
		}
	}
	int s=n+1,t=n+2;
	for(int i=1;i<=n;i++){
		if(b[i]>0) add(s,i,b[i]);
		else add(i,t,-b[i]);
	}
	printf("%lld\n",sum-solve(s,t));
}