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 Adrian
#include "debug.h"
#else
#define debug(...) 9999
#endif

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef complex<int> point;
#define F first
#define S second
#define ii pair<int,int>

/*
	Maximum Flow

	Complexity: O(n^2 * m) faster in most cases
	    O(min(n^(2/3), m^(1/2)) * m) in networks with unit capacities
	    O(n^(1/2) * m) in bipartite networks
	** be careful if lb(flow with lower bound) with flow_type **
*/

template<typename C, typename R = C, bool lb = false>
struct dinic
{
    typedef C flow_type;
    typedef R result_type;

    static_assert(std::is_arithmetic<flow_type>::value, "flow_type must be arithmetic");
    static_assert(std::is_arithmetic<result_type>::value, "result_type must be arithmetic");

    static const flow_type oo = std::numeric_limits<flow_type>::max();

    struct edge
    {
        int src; // not needed, can be deleted to save memory
        int dst;
        int rev;
        flow_type cap, flow;

        edge(int src, int dst, int rev, flow_type cap, flow_type flow) :
                src(src), dst(dst), rev(rev), cap(cap), flow(flow) {}
    };

    dinic(int n) : adj(n + 2*lb), que(n + 2*lb), level(n + 2*lb), edge_pos(n + 2*lb) {}

    int add_edge(int src, int dst, flow_type cap, flow_type rcap = 0) // if lb rcap is low
    {
        adj[src].emplace_back(src, dst, (int) adj[dst].size(), cap, lb ? rcap : 0);
        if (src == dst) adj[src].back().rev++;
        adj[dst].emplace_back(dst, src,  (int) adj[src].size() - 1, lb ? 0 : rcap, 0);
        return (int) adj[src].size() - 1 - (src == dst);
    }

    inline bool side_of_S(int u) { return level[u] == -1; }

    result_type max_flow(int source, int sink)
    {
        result_type flow = 0;
        while (true)
        {
            int front = 0, back = 0;
            std::fill(level.begin(), level.end(), -1);
            for (level[que[back++] = sink] = 0; front < back && level[source] == -1; ++front)
            {
                int u = que[front];
                for (const edge &e : adj[u])
                    if (level[e.dst] == -1 && rev(e).flow < rev(e).cap)
                        level[que[back++] = e.dst] = 1 + level[u];
            }
            if (level[source] == -1)
                break;
            std::fill(edge_pos.begin(), edge_pos.end(), 0);
            std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
            {
                if (from == sink)
                    return res;
                for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
                {
                    edge &e = adj[from][ept];
                    if (e.flow == e.cap || level[e.dst] + 1 != level[from]) continue;
                    flow_type push = find_path(e.dst, std::min(res, e.cap - e.flow));
                    if (push > 0)
                    {
                        e.flow += push;
                        rev(e).flow -= push;
                        if (e.flow == e.cap)
                            ++ept;
                        return push;
                    }
                }
                return static_cast<flow_type>(0);
            };
            for (flow_type f; (f = find_path(source, oo)) > 0;)
                flow += f;
        }
        return flow;
    }

    result_type max_flow_lb(int source, int sink)
    {
        int n = adj.size() - 2;
        vector<flow_type> delta(n + 2);
        for (int u = 0; u < n; ++u)
            for (auto &e : adj[u])
            {
                delta[u] -= e.flow;
                delta[e.dst] += e.flow;
            }

        result_type sum = 0;
        int s = n, t = n + 1;
        for (int u = 0; u < n; ++u)
        {
            if (delta[u] > 0)
            {
                add_edge(s, u, delta[u], 0);
                sum += delta[u];
            }
            else if (delta[u] < 0)
                add_edge(u, t, -delta[u], 0);
        }

        add_edge(sink, source, oo, 0);
        if (max_flow(s, t) != sum)
            return -1; // no solution

        result_type flow = adj[sink].back().flow;
        adj[sink].pop_back();
        adj[source].pop_back();
        return flow + max_flow(source, sink);
    }

    std::vector<std::vector<edge>> adj;
private:
    std::vector<int> que;
    std::vector<int> level;
    std::vector<int> edge_pos;

    inline edge& rev(const edge &e) { return adj[e.dst][e.rev]; }
};


int main() {
#ifdef Adrian
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    int n;
    cin>>n;

    vector<int> a(n), b(n);
    for(auto &i:a) cin>>i;
    for(auto &i:b) cin>>i;

    dinic<int> d(n + 2);
    int source = n, sink = n + 1, oo = 1e9;

    for(int i=0; i<n; i++)
    {
        for(int j=1; j<=a[i]; j++)
            if(a[i] % j == 0)
            {
                int k = i - 1;
                for(; k >= 0 && a[k] != j; k--);

                if(k >= 0) d.add_edge(i, k, oo);
            }

        if(b[i] >= 0) d.add_edge(source, i, b[i]);
        else d.add_edge(i, sink, -b[i]);
    }

    int ans = 0;
    for(auto i:b) ans += max(i, 0);

    cout<<ans - d.max_flow(source, sink)<<'\n';



    return 0;
}
