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 N = 3005;
int n, a[N], b[N];
long long cont[N];
bool used[N];

template <class T>
struct Dinic {
	struct Edge {
		int u, rev;
		T cap;
	};

	static const T MX = 1e10;

	int n, s, t;
	vector<int> level;
	vector<vector<Edge>> adjList;

	Dinic(int n):
		n(n), s(0), t(n - 1), level(n), adjList(n) {};

	void addEdge(int v, int u, T c) {
		adjList[v].push_back({u, (int) adjList[u].size(), c});
		adjList[u].push_back({v, (int) adjList[v].size() - 1, 0});
	}

	bool bfs() {
		queue<int> q;
		fill(level.begin(), level.end(), -1);

		q.push(s);
		level[s] = 0;
		while (!q.empty()) {
			int v = q.front();
			q.pop();

			if (v == t)
				return true;

			for (Edge e : adjList[v]) {
				if (e.cap <= 0 || level[e.u] != -1) continue;
				level[e.u] = level[v] + 1;
				q.push(e.u);
			}
		}

		return false;
	}

	T dfs(int v, T flow) {
		if (v == t)
			return flow;
		if (flow == 0)
			return 0;

		T cont = 0;
		for (Edge &e : adjList[v]) {
			if (e.cap <= 0 || level[e.u] <= level[v]) continue;
			T mnFlow = dfs(e.u, min(flow, e.cap));

			if (mnFlow > 0) {
				cont += mnFlow;
				flow -= mnFlow;
				e.cap -= mnFlow;
				adjList[e.u][e.rev].cap += mnFlow;
			}

			if (flow == 0) break;
		}
		return cont;
	}

	T maxFlow() {
		T flow, ans = 0;
		while (bfs()) {
			while ((flow = dfs(s, MX)) > 0) {
				ans += flow;
			}
		}
		return ans;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	Dinic<long long> mf(n + 2);

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}

	long long sum = 0;
	for (int i = 1; i <= n; i++) {
		if (b[i] >= 0) mf.addEdge(0, i, b[i]);
		else mf.addEdge(i, n + 1, -b[i]);

		set<int> seen;
		for (int j = i - 1; j > 0; j--) {
			if (a[i] % a[j] || seen.count(a[j])) continue;
			mf.addEdge(i, j, Dinic<long long>::MX);
			seen.insert(a[j]);
		}

		if (b[i] > 0)
			sum += b[i];
	}

	cout << sum - mf.maxFlow() << '\n';

	return 0;
}
