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 <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

template<typename T>
class MaxFlow {
public:
	MaxFlow() : RND(0) {
	}
    void setRND(int x = 0) { RND = max(0, x); }

	void init(int n, int _s, int _t) {
		graph.clear();
		graph.resize(n + 100);

		edges.clear();

		N = n;
		s = _s;
		t = _t;
		FLOW = 0;

		clock = 0;
		time.clear();
		time.resize(n, 0);
	}

	void addEdge(int u, int v, T w) {
		graph[u].push_back(addEdge(u, v, 0, w));
		graph[v].push_back(addEdge(v, u, 0, 0));
	}

	int maxFlow(vector<vector<int>>& G, int n, int s, int t) {
		init(G, n, s, t);
		return maxFlow();
	}

	T maxFlow() {
		for (int i = RND; i >= 0; --i) {
			FLOW += enlarge(1LL << i);
		}
		return FLOW;
	}

private:
	struct Edge {
	public:
		Edge(int u = -1, int v = -1, T f = 0, T c = 0) : from(u), to(v), flow(f), capacity(c) {
		}

		T remain() {
			return capacity - flow;
		}

		int from, to;
		T flow, capacity;
	};

	int N;
	int s;
	int t;
	T FLOW;
    int RND;

	vector<vector<int>> graph;
	vector<Edge> edges;

	int clock;
	vector<int> time;

	int addEdge(int u, int v, T flow, T cap) {
		int eidx = edges.size();
		edges.emplace_back(u, v, flow, cap);
		return eidx;
	}


	T enlarge(T req) {
		T res = 0;
		while (true) {
			++clock;
			T inc = dfs(s, req);
			if (inc == 0) {
				break;
			}
			res += inc;
		}
		return res;
	}

	T dfs(int u, T req) {
		time[u] = clock;
		if (u == t) {
			return req;
		}

		for (auto& eidx : graph[u]) {
			int v = edges[eidx].to;
			if (time[v] == clock) {
				continue;
			}
			if (edges[eidx].remain() >= req) {
				T res = dfs(v, req);
				if (res >= req) {
					edges[eidx].flow += res;
					edges[eidx ^ 1].flow -= res;
					return res;
				}
			}
		}

		return 0;
	}

};

class Solution {
public:
    long long solve(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int m = n + 10;
        int s = n + 1;
        int t = n + 2;
        MaxFlow<long long> mf;
        mf.init(m, s,  t);
        mf.setRND(17);

        vector<int> pos(111, -1);

        long long res = 0;
        for (int i = 0; i < n; ++i) {
            int x = A[i];
            int v = B[i];
            if (v >= 0) {
                res += v;
                mf.addEdge(s, i, v);
            } else {
                mf.addEdge(i, t, -v);
            }
            for (int j = 1; j <= x; ++j) {
                if (x % j == 0) {
                    if (pos[j] >= 0) {
                        mf.addEdge(i, pos[j], 1LL << 50);
                    }
                }
            }
            pos[x] = i;
        }
        
        res -= mf.maxFlow();
        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    Solution sol;

    int n;
    cin >> n;
    vector<int> A(n);
    vector<int> B(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> B[i];
    }

    cout << sol.solve(A, B) << '\n';

    return 0;
}