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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	3000
#define N_	(N + 2)
#define A	100
#define D	12	/* http://oeis.org/A066150 */
#define M_	(N + N * D)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int ij[M_], cc[M_ * 2], m_;
int *eh[N_], eo[N_], eo_[N_], n_;

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

void add(int i, int j, int c) {
	int h = m_++;

	ij[h] = i ^ j, cc[h << 1 | 0] = c;
	append(i, h << 1 | 0), append(j, h << 1 | 1);
}

int dd[N_];

int bfs(int s, int t) {
	static int qu[N + 2];
	int i, head, cnt;

	for (i = 0; i < n_; i++)
		dd[i] = n_;
	head = cnt = 0;
	dd[s] = 0, qu[head + cnt++] = s;
	while (cnt) {
		int d, o;

		i = qu[cnt--, head++], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			int h_ = eh[i][o];

			if (cc[h_]) {
				int h = h_ >> 1, j = i ^ ij[h];

				if (dd[j] > d) {
					dd[j] = d;
					if (j == t)
						return 1;
					qu[head + cnt++] = j;
				}
			}
		}
	}
	return 0;
}

int dfs(int i, int t, int c) {
	int d, o;

	if (i == t)
		return c;
	d = dd[i] + 1;
	for (o = eo_[i]; o--; ) {
		int h_ = eh[i][o];

		if (cc[h_]) {
			int h = h_ >> 1, j = i ^ ij[h], f;

			if (dd[j] == d && (f = dfs(j, t, min(c, cc[h_])))) {
				cc[h_] -= f, cc[h_ ^ 1] += f;
				eo_[i] = o + 1;
				return f;
			}
		}
	}
	dd[i] = n_, eo_[i] = 0;
	return 0;
}

int dinic(int s, int t) {
	int sum, f;

	sum = 0;
	while (bfs(s, t)) {
		memcpy(eo_, eo, n_ * sizeof *eo_);
		while ((f = dfs(s, t, INF)))
			sum += f;
	}
	return sum;
}

int main() {
	static int aa[N + 1], bb[N + 1], ii[A + 1];
	int n, s, t, i, j, sum;

	scanf("%d", &n), n_ = n + 2, s = 0, t = n + 1;
	for (i = 0; i < n_; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (i = 1; i <= n; i++)
		scanf("%d", &aa[i]);
	sum = 0;
	for (i = 1; i <= n; i++) {
		scanf("%d", &bb[i]);
		if (bb[i] >= 0)
			sum += bb[i], add(s, i, bb[i]);
		else
			add(i, t, -bb[i]);
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j < i; j++)
			if (ii[aa[j]] == j && aa[i] % aa[j] == 0)
				add(i, j, INF);
		ii[aa[i]] = i;
	}
	printf("%d\n", sum - dinic(s, t));
	return 0;
}
