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;

#define rep(i, a, n) for(int i=(a); i<(n); ++i)
#define per(i, a, n) for(int i=(a); i>(n); --i)
#define pb emplace_back
#define mp make_pair
#define clr(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x & -x)
#define fi first
#define se second
#define lson o<<1
#define rson o<<1|1
#define gmid l[o]+r[o]>>1

using LL = long long;
using ULL = unsigned long long;
using pii = pair<int,int>;
using PLL = pair<LL, LL>;
using UI = unsigned int;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1.0);

const int N = 3010;
const int M = 101;

int n, a[N];
int tar, cur[N], d[N], vis[M];
int head, tail, Q[N];

struct Edge{
	int from, to, cap, flow;
	Edge(){}
	Edge(int from, int to, int cap):from(from),to(to),cap(cap){
		flow = 0;
	}
};
vector<Edge> G;
vector<int> V[N];

void add_edge(int from, int to, int cap){
	G.pb(from, to, cap);
	G.pb(to, from, 0);
	int x = G.size();
	V[from].pb(x - 2);
	V[to].pb(x - 1);
}

bool bfs(){
	rep(i, 0, tar + 1)	d[i] = -1;
	d[0] = 0;
	int x = 0;
	head = tail = 0;
	Q[tail++] = x;
	while(head < tail){
		x = Q[head++];
		for(int j : V[x]){
			Edge &e = G[j];
			if(e.cap>e.flow && d[e.to]==-1){
				d[e.to] = d[x] + 1;
				Q[tail++] = e.to;
			}
		}
	}
	return d[tar] != -1;
}

int dfs(int x, int v){
	if(x==tar || v==0)	return v;
	int flow = 0, f;
	for(int &i=cur[x]; i<V[x].size(); ++i){
		int j = V[x][i];
		Edge &e = G[j];
		if(d[e.to]==d[x]+1 && (f=dfs(e.to, min(e.cap-e.flow, v)))>0){
			flow += f;
			e.flow += f;
			v -= f;
			G[j^1].flow -= f;
			if(!v)	break;
		}
	}
	return flow;
}

int main(){
	bool flag;
	scanf("%d", &n);
	int sum = 0, x;
	rep(i, 1, n+1)	scanf("%d", a+i);
	tar = n + 1;
	memset(vis, -1, sizeof(vis));
	rep(i, 1, n+1){
		scanf("%d", &x);
		if(x > 0){
			sum += x;
			add_edge(0, i, x);
		} else if(x < 0){
			add_edge(i, tar, -x);
		}
		rep(j, 1, a[i]+1){
			if(vis[j] != -1 && a[i]%j==0){
				add_edge(i, vis[j], inf);
			}
		}
		vis[a[i]] = i;
	}
	while(bfs()){
		rep(i, 0, tar + 1)	cur[i] = 0;
		sum -= dfs(0, inf);
	}
	printf("%d\n", sum);
	return 0;
}