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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }


struct MaxFlow {
	int n;
	vector<int> ghead, gnxt, gto; vector<ll> gcap;
	vector<int> d; queue<int> q; vector<int> cur;

	void init(int _n) { n = _n; ghead = vector<int>(n, -1); gnxt = gto = vector<int>(); gcap = vector<ll>(); }
	int addedgewithflow(int a, int b, ll cap, ll flow) {
		gnxt.PB(ghead[a]); ghead[a] = SZ(gnxt) - 1; gto.PB(b); gcap.PB(cap - flow);
		gnxt.PB(ghead[b]); ghead[b] = SZ(gnxt) - 1; gto.PB(a); gcap.PB(flow);
		return SZ(gnxt) - 2;
	}
	int addedge(int a, int b, ll cap) { return addedgewithflow(a, b, cap, 0); }
	ll dfs(int at, int t, ll rem) {
		ll ret = 0;
		if (at == t) return rem;
		if (d[at] >= d[t]) return 0;
		for (; cur[at] != -1; cur[at] = gnxt[cur[at]]) {
			int to = gto[cur[at]]; ll cap = gcap[cur[at]];
			if (d[to] != d[at] + 1 || cap == 0) continue;
			ll now = dfs(to, t, min(cap, rem));
			rem -= now; ret += now;
			if (gcap[cur[at]] != LLONG_MAX) gcap[cur[at]] -= now;
			if (gcap[cur[at] ^ 1] != LLONG_MAX) gcap[cur[at] ^ 1] += now;
			if (rem == 0) return ret;
		}
		return ret;
	}
	ll solve(int s, int t) {
		ll ret = 0;
		while (true) {
			d = vector<int>(n, INT_MAX); q = queue<int>();
			d[s] = 0, q.push(s);
			while (!q.empty() && d[t] == INT_MAX) {
				int at = q.front(); q.pop();
				for (int x = ghead[at]; x != -1; x = gnxt[x]) {
					int to = gto[x];
					if (gcap[x] == 0 || d[to] != INT_MAX) continue;
					d[to] = d[at] + 1, q.push(to);
				}
			}
			if (d[t] == INT_MAX) return ret;
			cur = ghead;
			ret += dfs(s, t, LLONG_MAX);
		}
	}
	ll getflow(int x) { return gcap[x ^ 1]; }
};

const int MAXN = 3000;

int n;
int a[MAXN];
int b[MAXN];

MaxFlow g;

ll solve() {
	int sid = n, tid = n + 1;
	g.init(n + 2);
	ll ret = 0;
	REP(i, n) if (b[i] > 0) ret += b[i], g.addedge(sid, i, b[i]);
	REP(i, n) { set<int> seen; for (int j = i - 1; j >= 0; --j) if (a[i] % a[j] == 0 && !seen.count(a[j])) { seen.insert(a[j]); g.addedge(i, j, LLONG_MAX); } }
	REP(i, n) if (b[i] < 0) g.addedge(i, tid, -b[i]);
	ret -= g.solve(sid, tid);
	return ret;
}

void run() {
	scanf("%d", &n);
	REP(i, n) scanf("%d", &a[i]);
	REP(i, n) scanf("%d", &b[i]);
	printf("%lld\n", solve());
}

int main() {
	run();
	return 0;
}
