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 <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define pb push_back
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<int, int> P;
const int maxn = 3010;
const int maxm = 1e5+10;
const int INF = 1e9 + 9;
struct Edge
{
    int u, v, f, nxt;
} edges[maxm];
int head[maxn], tot, n;
int cost[maxn], val[maxn], pos[maxn];
void addEdge(int u, int v, int f)
{
    edges[tot].u = u;
    edges[tot].v = v;
    edges[tot].f = f;
    edges[tot].nxt = head[u];
    head[u] = tot++;
    edges[tot].u = v;
    edges[tot].v = u;
    edges[tot].f = 0;
    edges[tot].nxt = head[v];
    head[v] = tot++;
}
int depth[maxn], cur[maxn];
bool bfs(int S, int T) // åˆ†å±‚å›¾
{
    queue<int> Q;
    memset(depth, 0, sizeof(depth));
    depth[S] = 1;
    Q.push(S);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; ~i; i = edges[i].nxt)
        {
            if (edges[i].f > 0 && depth[edges[i].v] == 0)
            {
                depth[edges[i].v] = depth[u] + 1;
                Q.push(edges[i].v);
                if (edges[i].v == T)
                    return true;
            }
        }
    }
    return false;
}
int dfs(int u, int T, int flow) // æ‰¾å¢žå¹¿è·¯
{
    if (u == T)
        return flow;
    for (int &i = cur[u]; ~i; i = edges[i].nxt) // &ç¬¦å·ï¼Œiæ”¹å˜åŒæ—¶ä¹Ÿæ”¹å˜cur[u]çš„å€¼ï¼Œè¾¾åˆ°è®°å½•å½“å‰å¼§çš„ç›®çš„
    {
        if (depth[edges[i].v] == depth[u] + 1 && edges[i].f != 0)
        {
            int sub = dfs(edges[i].v, T, min(flow, edges[i].f)); // å‘ä¸‹å¢žå¹¿
            if (sub > 0)
            {
                edges[i].f -= sub;
                edges[i ^ 1].f += sub;
                return sub;
            }
        }
    }
    return 0;
}
int Dinic(int n, int S, int T)
{
    int ans = 0;
    while (bfs(S, T))
    {
        for (int i = 0; i <= n; i++) // //æ¯ä¸€æ¬¡å»ºç«‹å®Œåˆ†å±‚å›¾åŽéƒ½è¦æŠŠcurç½®ä¸ºæ¯ä¸€ä¸ªç‚¹çš„ç¬¬ä¸€æ¡è¾¹
            cur[i] = head[i];
        while (int f = dfs(S, T, INF))
        {
            ans += f;
        }
    }
    return ans;
} //næœ€å¤šçš„ç‚¹æ•°ï¼ŒSä¸ºæºç‚¹ï¼ŒTä¸ºæ±‡ç‚¹
/*
tot=0;
memset(head,-1,sizeof(head));
addEdge(u,v,c);
*/
int main()
{
    IOS;
    mem(head, -1);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    int s = 0, t = n + 1;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (cost[i] >= 0)
        {
            addEdge(s, i, cost[i]);
            //cout << "addedge " << s << " " << i << " " << cost[i] << endl;
            sum += cost[i];
        }
        else
        {
            //cout << "addedge " << i << " " << t << " " << -cost[i] << endl;
            addEdge(i, t, -cost[i]);
        }

        for (int j = 1; j <= val[i]; j++)
        {
            if (val[i] % j == 0 && pos[j] != 0)
            {
                addEdge(i,  pos[j], 1e7);
                //cout << "addedge " << i << " " << pos[j] << " INF" << endl;
            }
        }
        pos[val[i]] = i;
    }
    int ans = Dinic(t, s, t);
    //cout << ans << endl;
    cout << sum - ans << endl;
    return 0;
}
/*
4
1 1 1 1
3 4 -3 -2
*/
		 		  	 	 	   		  			 	   	