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; 

#ifdef LOCAL
    #include "debug.h"
    #define input freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#else
    #define debug(...) 4
    #define input 4
#endif

using ll = long long;
//const int mod = 998244353;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;

class Dinic {
    private:
        const static ll INF = 8*(ll)1e18;
        struct Edge {
            const int t; // Endpoint
            ll a; // Admissible flow
            Edge(int tar, ll cap = INF) : t(tar), a(cap) {}
        };
 
        vector<Edge> edges;
        vector<vector<int>> conns;
        vector<int> dist, act_ind;
 
        ll push(int ei, ll v) {
            edges[ei].a -= v;
            edges[ei ^ 1].a += v;
            return v;
        }
        void calcDists(int sink) {
            for (int& v : dist) v = -1;
            dist[sink] = 0;
            vector<int> que = {sink};
            for (int j = 0; j < que.size(); ++j) {
                for (auto ei : conns[que[j]]) {
                    int t = edges[ei].t;
                    if (edges[ei^1].a > 0 && dist[t] == -1) {
                        dist[t] = dist[que[j]] + 1;
                        que.push_back(t);
                    }
                }
            }
        }
        ll dfsFlow(int i, int sink, ll cap) {
            if (i == sink) return 0;
            for (int& j = act_ind[i]; j < conns[i].size(); ++j) {
                int ei = conns[i][j];
                int t = edges[ei].t;
                if (dist[t] != dist[i] - 1 || edges[ei].a == 0) continue;
 
                ll subcap = min(cap, edges[ei].a);
                cap -= push(ei, subcap - dfsFlow(t, sink, subcap));
                if (! cap) return 0;
            }
            return cap;
        }
    public:
        Dinic(int n) : conns(n), dist(n), act_ind(n) {}
 
        int addEdge(int s, int t, ll c = INF, bool dir = 1) {
            debug(s, t, c);
            int i = edges.size() / 2;
            edges.emplace_back(t, c);
            edges.emplace_back(s, dir ? 0 : c);
            conns[s].push_back(2*i);
            conns[t].push_back(2*i+1);
            return i;
        }
        ll pushFlow(int source, int sink) {
            for (ll res = 0;;) {
                calcDists(sink);
                if (dist[source] == -1) return res;
                for (int& v : act_ind) v = 0;
                res += INF - dfsFlow(source, sink, INF);
            }
        }
        // Returns a min-cut containing the sink
        vector<int> minCut() {
            vector<int> res;
            for (int i = 0; i < dist.size(); ++i) {
                if (dist[i] == -1) res.push_back(i);
            }
            return res;
        }
        // Gives flow on edge assuming it is directed/undirected. Undirected flow is signed.
        ll getDirFlow(int i) const { return edges[2*i+1].a; }
        ll getUndirFlow(int i) const { return (edges[2*i+1].a - edges[2*i].a) / 2; }
};
signed main() {
    input;
    cin.tie(nullptr) -> sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while(t--) {    
        int n;
        cin >> n;
        int a[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];

        }
        int b[n];
        for(int i = 0; i < n; i++) {
            cin >> b[i];
        }
        Dinic d(n + 2);
        vector<int> last(200, -1);
        for (int i = 0; i < n; i++) {
            for (int x = 1; x <= a[i]; x++)
                if (a[i] % x == 0 && last[x] >= 0)
                    d.addEdge(last[x], i);
     
            last[a[i]] = i;
        }
        int src = n, sink = n + 1;
        ll sum = 0;
        for(int i = 0; i < n; i++) {
            if(b[i] > 0) {
                d.addEdge(i, sink, b[i]);
                sum += b[i];
            }
            else {
                d.addEdge(src, i, -b[i]);
            }
        }
        cout << sum - d.pushFlow(src, sink) << '\n';

    }
}
