C. 连锁商店 （暴力优化）

比特山是一个旅游胜地，它一共有 nn 个景点，按照海拔高度从低到高依次编号为 11 到 nn。为了更好地帮助游客们欣赏这里的风景，人们在上面搭建了 mm 条缆车路线。每条缆车路线只可能把游客们从某个海拔较低的景点运送到另一个海拔较高的景点。

在每个景点都有一家纪念品连锁商店，其中第 ii 个景点的商店隶属第 cici 号公司，两家连锁店 (i,j)(i,j) 隶属同一公司当且仅当 ci=cjci=cj。每家公司都有新客优惠活动，其中第ii家公司对于新客的优惠红包为 wiwi 元，一旦领取了隶属该公司的某家连锁店的一份红包，就不能再领取该公司所有分店的红包。

你正在 11 号景点，你将会搭乘缆车去往各个景点，每到一个景点，你都可以领取该景点的连锁商店的新客优惠红包（包括 11 号景点）。当然，同一家公司的红包最多只能领一次。请写一个程序，对于每个可能的终点 kk，找到一条从 11 号景点出发到达 kk 号景点的游览路线，使得可以领取到总金额最多的优惠红包。

Input

第一行包含两个正整数 n,mn,m (2≤n≤362≤n≤36, 1≤m≤n(n−1)21≤m≤n(n−1)2)，分别表示景点的数量以及缆车路线的数量。

第二行包含 nn 个正整数 c1,c2,…,cnc1,c2,…,cn (1≤ci≤n1≤ci≤n)，依次表示每个景点的商店所隶属的公司。

第三行包含 nn 个正整数 w1,w2,…,wnw1,w2,…,wn (1≤wi≤1061≤wi≤106)，依次表示每家公司的新客优惠红包的金额。

接下来 mm 行，每行两个正整数 ui,viui,vi (1≤ui

Output

输出 nn 行，第 ii 行输出一个整数，即从 11 号景点出发到达 ii 号景点时，领取的优惠红包的总金额的最大值。

Example

input

Copy

5 5
1 2 2 3 4
1 4 5 9 3
1 2
2 3
3 5
1 4
4 5

output

Copy

1
5
5
6
15

思路：点很少但是会有一个点连很多个点的情况

那么我们就考虑，比如说1-6是一条路，1-2-6也是一条路

那么显然1-2-6走的点更多，能收到更多红包

那么我们就用Floyd优化一下，如果i j之间有一条路，i k，k j之间也有路，那么把i j之间的路给删掉

然后正常深搜就行

#include<bits/stdc++.h>
using namespace std;
int n,m;
int c[40];
int w[40];
vector<int> v[100];
int g[40][40];
int ans[40];
map<int,int> mp;
void dfs(int u,int con){//走到第u个点的时候，当前得到红包的值
	ans[u]=max(ans[u],con);//更新
	for(auto i:v[u]){//遍历与u相连的点
	//	cout<<"u=="<<u<<" i=="<<i<<endl;
		if(mp[c[i]]==0){//如果没被收过
			mp[c[i]]=1;
			dfs(i,con+w[c[i]]);
			mp[c[i]]=0;//回溯
		}else dfs(i,con);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>w[i];
	while(m--){
		int a,b;
		cin>>a>>b;
		g[a][b]=1;
	}
	//Floyd优化图
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(g[i][k]&&g[i][j]&&g[j][k]){
					g[i][k]=0;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(g[i][j]){
				v[i].push_back(j);
			}
		}
	}
	ans[1]=w[c[1]];
	mp[c[1]]=1;
	dfs(1,w[c[1]]);
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
}