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 ;
const int maxn = 6e5 + 10 ;
const int inf = 0x3f3f3f3f ;
struct Dinic
{
    int tot ;
    int Next[maxn],last[maxn],to[maxn],flow[maxn],q[maxn],dis[maxn],S,T;
    void init()
    {
        tot = 1 ;
        memset(last , 0 , sizeof(last)) ;
    }
    void add(int x,int y,int v) {
        Next[++tot]=last[x]; last[x]=tot; to[tot]=y; flow[tot]=v;
    }
    void auto_add(int x,int y,int w) {
        add(x,y,w);
        add(y,x,0);
    }
    bool bfs() {
        int l=0,r=1; q[1]=S;
        for (int i=1;i<=T;i++) dis[i]=0;
        dis[S]=1;
        while (l<r) {
            int k=q[++l];
            for (int i=last[k];i;i=Next[i]) {
                if (dis[to[i]]||!flow[i]) continue;
                dis[q[++r]=to[i]]=dis[k]+1;
            }
        }
        return dis[T]>0;
    }
    int dfs(int x,int y) {
        if (!y) return 0;
        if (x==T) return y;
        int sum=0;
        for (int i=last[x];i;i=Next[i]) {
            if (dis[to[i]]!=dis[x]+1||!flow[i]) continue;
            int tmp=dfs(to[i],min(y-sum,flow[i]));
            if (tmp) {
                sum+=tmp;
                flow[i]-=tmp;
                flow[i^1]+=tmp;
            }
            else dis[to[i]]=0;
            if (sum==y) return sum;
        }
        return sum;
    }
    int dinic() {
        int ans=0;
        while (bfs()) ans+=dfs(S,inf);
        return ans;
    }
} dinic ;
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    int n ;
    cin >> n ;
    vector<int> a(n + 1) , b(n + 1) ;
    for(int i = 1 ; i <= n ; i ++)  cin >> a[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> b[i] ;
    dinic.init() ;
    dinic.S = n + 1 ;
    dinic.T = n + 2 ;
    int ans = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(b[i] > 0)  
        {
            ans += b[i] ;
            dinic.auto_add(dinic.S , i , b[i]) ;
        }
        else if(b[i] < 0)
        {
            dinic.auto_add(i , dinic.T , -b[i]) ;
        }
    }
    vector<int> lst(101 , -1) ;
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= 100 ; j ++)
            if(a[i] % j == 0)
            {
                if(lst[j] != -1)
                    dinic.auto_add(i , lst[j] , inf) ;
            }
        lst[a[i]] = i ;
    }
    cout << ans - dinic.dinic() << '\n' ;
    return 0 ;
}