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;
typedef long long ll;
const int N=1e4+5;
const int M=1e6+5;
const int mod=1e9+7;
const int INF=1e9+7;
int n,m,T,k,d;
int a[N],b[N];
int vis[N];
int s,t,maxflow=0,lowflow;
struct node {
    int to,w,next,flow;
} edge[M];
int head[N],cnt=1,dep[N],inque[N],cur[N];
void add(int u,int v,int w) {
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].flow=0;
    head[u]=cnt;
}
struct Maxflow {
    bool bfs() {
        queue<int>q;
        memset(dep,-1,sizeof dep);
        dep[s]=0;
        q.push(s);
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            inque[u]=0;
            for(int i=head[u]; i; i=edge[i].next) {
                int v=edge[i].to,w=edge[i].w;
                if(dep[v]==-1&&w) {
                    dep[v]=dep[u]+1;
                    q.push(v);
                }
            }
        }
        return dep[t]!=-1;
    }
    int dfs(int u,int flow) {
        if(u==t) {
            return flow;
        }
        int rlow=0,used=0;
        for(int i=cur[u]; i; i=edge[i].next) {
            int v=edge[i].to,w=edge[i].w;
            if(w&&dep[v]==dep[u]+1) {
                if(rlow=dfs(v,min(flow,w))) {
                    used+=rlow;
                    flow-=rlow;
                    edge[i].w-=rlow;
                    edge[i^1].w+=rlow;
                    edge[i].flow+=rlow;
                    edge[i^1].flow-=rlow;
                    if(flow==0)
                        break;
                }
            }
        }
        if(!used)dep[u]=-1;
        return used;
    }
    int Dinic() {
        maxflow=0;
        while(bfs()) {
            for(int i=1; i<=t; i++)
                cur[i]=head[i];
            maxflow+=dfs(s,INF);
        }
        return maxflow;
    }
    void init() {
        cnt=1;
        memset(head,0,sizeof head);
    }
    void addedge(int u,int v,int w) {

        add(u,v,w);
        add(v,u,0);
    }
} ac;
int f[N];
int FIND(int x) {
    return x==f[x]?x:f[x]=FIND(f[x]);
}
void join(int x,int y) {
    x=FIND(x);
    y=FIND(y);
    if(x==y)return ;
    f[x]=y;
}
vector<int>G[N];
int main() {

    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]);
    for(int i=1; i<=n; i++)f[i]=i;
    for(int i=1; i<=100; i++) {
        for(int j=i+i; j<=100; j+=i) {
            G[j].push_back(i);
        }
    }
    ac.init();
    s=n+1,t=n+2;
    int sum=0;
    for(int i=1; i<=n; i++) {
        if(b[i]>0)sum=sum+b[i],ac.addedge(s,i,b[i]);
        else ac.addedge(i,t,-b[i]);
        for(int i=1; i<=100; i++)vis[i]=0;
        for(int j=i-1; j>=1; j--) {
            if(a[i]%a[j]==0&&vis[a[j]]==0) {
                ac.addedge(i,j,INF);
                vis[a[j]]=1;
                for(int fac:G[a[j]]) vis[fac]=1;
            }
        }
    }
    int ans=sum-ac.Dinic();
    cout<<ans<<endl;







}
