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.
// optimization flags
#pragma GCC target ("avx2")
// TODO: safe?
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
// including std
#include <bits/stdc++.h>
using namespace std;
// use solve instead of main for easy fast input
void solve(); void subcases(); void precompute();
int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout<<setprecision(17); subcases(); }
// generic printing of iterators
template<typename T_container,typename T = typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream& os,const T_container& v){ os << '{'; string sep; for (const T& x: v) os<< sep << x, sep = ", "; return os << '}'; }
// python-ish read and print functions
template<typename T> T read(){ T x; cin >> x; return x; }
template<typename T> void read(T& x) { cin >> x; }
template<typename T> void print(const T& x) { cout << x<< "\n"; }
// macro/template hackery to get quick debug info
template<typename L> void DEBUG_(const char* str, L& last) { cout << str << " = " << last << endl; }
template<typename H, typename ...T> void DEBUG_(const char* str, H& val, T&... tail) {
	const char* comma = strchr(str, ',');
	cout << regex_replace(string(str, comma), regex("^ +| +$|( ) +"), "$1") << " = " << val << ", ";
	DEBUG_(comma+1, tail...);
}
// f should be monotone increasing mapping integers to booleans,
// i.e. falses and then trues (outputs whether input is 'at least' good)
// returns the first true value of f in [lo, hi) or else hi
template<class F>
int bsearch(int lo, int hi, F f) {
	while (hi > lo) {
		int mid = (lo + hi) / 2;
		if (f(mid)) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}
#define DEBUG(...) DEBUG_(#__VA_ARGS__, __VA_ARGS__)
// macro hackery to generate new names
#define CONCAT_(x,y) x##y
#define CONCAT(x,y) CONCAT_(x,y)
#define FRESHVAR() CONCAT(__FRESHVAR__, __COUNTER__)
// use 64-bit integers by default (make sure to actually submit in 64 bit)
#define int int_fast64_t
#define db double
// iterator utility defines
#define AR array
#define IT(x) begin(x), end(x)
#define sz(x) ((int)(x.size()))
// loop utility defines
#define TIMES_(i,n) for (int i = (n); i > 0; i--)
#define TIMES(n) TIMES_(FRESHVAR(), n)
#define FOR(i,n) for (int i = 0; i < (n); i++)
#define FORS(i,s,n) for (int i = (s); i < (n); i++)
#define FOR1(i,n) for (int i = 1; i <= (n); i++)
#define FORR(i,n) for (int i = (n) - 1; i >= 0; i--)
#define FORBIT(idx,v,m) for (int idx = 0, v = 1; idx < (m); idx++, v <<= 1)
// common function defines
#define caseout(x) do { print(x); return; } while (0)
#define pb push_back
#define vi vector<int>
#define mp make_pair
#define ri read<int>

const string NOYES[2] = {"NO","YES"};
const string NoYes[2] = {"No","Yes"};
const int INF = numeric_limits<int>::max() / 10;

// UTILITY PASTE
#define rep(i, a, b) for(int i = a; i < (b); ++i)
using ll = long long;
struct Dinic {
	struct Edge {
		int to, rev;
		ll c, oc;
		ll flow() { return max(oc - c, 0LL); } // if you need flows
	};
	vi lvl, ptr, q;
	vector<vector<Edge>> adj;
	Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
	void addEdge(int a, int b, ll c, int rcap = 0) {
		adj[a].push_back({b, sz(adj[b]), c, c});
		adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
	}
	ll dfs(int v, int t, ll f) {
		if (v == t || !f) return f;
		for (int& i = ptr[v]; i < sz(adj[v]); i++) {
			Edge& e = adj[v][i];
			if (lvl[e.to] == lvl[v] + 1)
				if (ll p = dfs(e.to, t, min(f, e.c))) {
					e.c -= p, adj[e.to][e.rev].c += p;
					return p;
				}
		}
		return 0;
	}
	ll calc(int s, int t) {
		ll flow = 0; q[0] = s;
		rep(L,0,31) do { // 'int L=30' maybe faster for random data
			lvl = ptr = vi(sz(q));
			int qi = 0, qe = lvl[s] = 1;
			while (qi < qe && !lvl[t]) {
				int v = q[qi++];
				for (Edge e : adj[v])
					if (!lvl[e.to] && e.c >> (30 - L))
						q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
			}
			while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
		} while (lvl[t]);
		return flow;
	}
	bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
// END UTIL

void subcases() {
	precompute();
	//TIMES(ri()) solve();
	solve();
}

void precompute() {

}

const int maxN = 3005;
int n, a[maxN], b[maxN], last[105];

void solve() {
	cin >> n;
	FOR1(i, n) cin >> a[i];
	FOR1(i, n) cin >> b[i];
	int sum = 0;
	Dinic g(n+2);
	FOR1(i, n) {
		if (b[i] >= 0) g.addEdge(0, i, b[i]), sum += b[i];
		else g.addEdge(i, n+1, -b[i]);
		FOR1(j, 100) if (last[j] && a[i] % j == 0) g.addEdge(i, last[j], INF);
		last[a[i]] = i;
	}
	//print(g.calc(0, n+1));
	print(sum - g.calc(0, n+1));
}
