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 <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=3005,MAXM=60005,Inf=0x7fffffff;
struct Edge{
	int to,cap,next;
	Edge(int to=0,int cap=0,int next=0){
		this->to=to;
		this->cap=cap;
		this->next=next;
	}
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Clear(){mem(head,-1);edge_cnt=0;}//�ߴ�0��ʼ��� 
void Insert(int u,int v,int c){
	edge[edge_cnt]=Edge(v,c,head[u]);
	head[u]=edge_cnt++;
	edge[edge_cnt]=Edge(u,0,head[v]);
	head[v]=edge_cnt++;
}
struct Dinic{
	int s,t;
	int pos[MAXN],vis[MAXN],dis[MAXN];
	bool bfs(int k){
		queue<int>q;
		q.push(s);
		vis[s]=k,dis[s]=0,pos[s]=head[s];
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];~i;i=edge[i].next){
				int v=edge[i].to;
				if(vis[v]!=k&&edge[i].cap){
					vis[v]=k,dis[v]=dis[u]+1,pos[v]=head[v];
					q.push(v);
					if(v==t)
					return true;
				}
			}
		}
		return false;
	}
	int dfs(int u,int max_flow){
		if(u==t||!max_flow)
		return max_flow;
		int flow=0,temp_flow;
		for(int &i=pos[u];~i;i=edge[i].next){
			int v=edge[i].to;
			if(dis[u]+1==dis[v]&&(temp_flow=dfs(v,min(max_flow,edge[i].cap)))){
				edge[i].cap-=temp_flow;
				edge[i^1].cap+=temp_flow;
				flow+=temp_flow;
				max_flow-=temp_flow;
				if(!max_flow)
				break;
			}
		}
		return flow;
	}
	int Maxflow(int s,int t){
		this->s=s;this->t=t;
		int ans=0,k=0;
		mem(vis,0);
		while(bfs(++k))
		ans+=dfs(s,Inf);
		return ans;
	}
}solver;
const int MAXV=105;
int a[MAXN],b[MAXN],last[MAXV];
int main()
{
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	int n=read_int(),s=0,t=n+1,ans=0;
	Clear();
	_rep(i,1,n)
	a[i]=read_int();
	_rep(i,1,n){
		b[i]=read_int();
		if(b[i]>0)
		Insert(s,i,b[i]),ans+=b[i];
		else if(b[i]<0)
		Insert(i,t,-b[i]);
	}
	_rep(i,1,n){
		_for(j,1,MAXV){
			if(a[i]%j==0&&last[j])
			Insert(i,last[j],Inf);
		}
		last[a[i]]=i;
	}
	enter(ans-solver.Maxflow(s,t));
	return 0;
}
