Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

int a[MAXN],b[MAXN];

struct edge

{

	int to,nxt,f;

}e[(MAXN * 2 + MAXN * MAXN) * 2];

int edgenum = 0;

#define MAXP (MAXN * 2)

int lin[MAXP] = {0};

void add(int a,int b,int f)

{ 

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int ch[MAXP];

int s,t;

bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

bool check1(int a,int b)

{

	long long s = 1ll * a * a + 1ll * b * b;

	long long k = sqrt(s);

	if(k * k == s)return true;

	else return false;

}

bool check2(int a,int b)

{

	return (gcd(a,b) == 1);

}

int main()

{freopen("t.in","r",stdin); 

	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]);

	s = n + 1;t = s + 1;

	memset(lin,-1,sizeof(lin));

	int sum = 0;

	for(int i = 1;i <= n;++i)

	{

		if(a[i] & 1)add(s,i,b[i]);

		else add(i,t,b[i]);

		sum += b[i];

	}

	for(int i = 1;i <= n;++i)if((a[i] & 1) == 1)

		for(int j = 1;j <= n;++j)if((a[j] & 1) == 0)

			if(check1(a[i],a[j]) && check2(a[i],a[j]))add(i,j,INF);

	cout << sum - dinic() << endl;

	return 0;

}