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;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 3e3 + 5;
const int MAXA = 1e2 + 5;
const int inf = 0x3f3f3f3f;

template<const int MAXN,const int MAXM>
struct Max_Flow
{
	struct Edge
	{
		int next,to,flow;
	}e[MAXM<<1];
	int head[MAXN],etot;
	inline void add_one(int u,int v,int flow)
	{
		e[++etot] = (Edge){ head[u],v,flow};
		head[u] = etot;
	}
	inline void add_edge(int u,int v,int flow){ add_one(u,v,flow); add_one(v,u,0);}
	
	int n,s,t;
	int dep[MAXN], cur[MAXN];
	inline void clear(void){ memset(head,-1,sizeof(head)); etot = -1;}
	inline void init(int _n,int _s,int _t){ n=_n; s=_s; t=_t;}
	Max_Flow(void){ clear();}
	inline bool bfs(void)
	{
		for(int i=1; i<=n; ++i) dep[i] = -1, cur[i] = head[i];
		queue<int> q;
		dep[s] = 0; q.push(s);
		while(q.size())
		{
			int u = q.front(); q.pop();
			for(int i=head[u]; ~i; i=e[i].next) if(e[i].flow)
			{
				int v = e[i].to;
				if(dep[v] == -1) dep[v] = dep[u] + 1, q.push(v);
			}
		}
		return ~dep[t];
	}
	int dfs(int u,int maxf)
	{
		if(u == t || !maxf) return maxf;
		int res = 0;
		for(int &i=cur[u], f; ~i; i=e[i].next)
			if(e[i].flow && dep[e[i].to] == dep[u] + 1 && (f = dfs(e[i].to, min(maxf, e[i].flow))))
			{
				e[i].flow -= f; e[i^1].flow += f;
				res += f; maxf -= f;
				if(!maxf) return res;
			}
		return res;
	}
	inline int dinic(void)
	{
		int res = 0;
		while(bfs()) res += dfs(s,inf);
		return res;
	}
};

int a[MAXN], b[MAXN];
bitset<MAXA> fact[MAXA];
Max_Flow<MAXN, MAXN * MAXA> mf;

int main(void)
{
	for(int i=1; i<=100; ++i)
		for(int j=1; j<=i; ++j)
			if(i%j == 0) fact[i][j] = 1;
	
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	for(int i=1; i<=n; ++i) scanf("%d",&b[i]);
	
	for(int i=1; i<=n; ++i)
	{
		bitset<MAXA> cur;
		for(int j=i-1; j>=1; --j) if(a[i] % a[j] == 0)
		{
			if(a[j] == a[i]){ mf.add_edge(i,j,inf); break;}
			if(cur[a[j]]) continue;
			mf.add_edge(i,j,inf); cur |= fact[a[j]];
		}
	}
	
	ll ans = 0;
	int s = n+1, t = n+2;
	for(int i=1; i<=n; ++i)
	{
		if(b[i] < 0) mf.add_edge(i,t,-b[i]);
		else ans += b[i], mf.add_edge(s,i,b[i]);
	}
	mf.init(t,s,t);
	
	printf("%lld",ans - mf.dinic());
	return 0;
}
