Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了~

机器人们都想知道谁是最勇敢的，于是它们比赛搬运一些物品。

它们到了一个仓库，里面有n个物品，每个物品都有一个价值Pi和重量Wi，但是有些物品放在一起会爆炸，并且爆炸具有传递性。（a和b会爆炸、b和c会爆炸则a和c会爆炸）
机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备，于是它们想知道在能力范围内，它们最多可以拿多少价值的物品。

你能帮助它们吗？

输入格式

输出格式

样例输入1[复制]

3 10 1100 1200 510 51 2

样例输出1[复制]

210

/*并查集分组，分组背包*/#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>using namespace std;const int maxn = 1005;struct ITM{    int v;    int w;}temp;int n,c,k,f[maxn],v[maxn],w[maxn],dp[maxn];int u1,u2,r;int cnt,tran[maxn],now;bool vis[maxn];vector<ITM> itm[maxn];int findf(int x){    return x == f[x] ? x : f[x] = findf(f[x]);}int read(){    char ch=getchar();    int f=1,x=0;    while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();};    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();};    return x*f;}int main(){    n = read();    c = read();    k = read();    for(int i = 1;i <= n;i++) f[i] = i;    for(int i = 1;i <= n;i++){        v[i] = read();        w[i] = read();    }    for(int i = 1;i <= k;i++){        u1 = read();        u2 = read();        u1 = findf(u1);        u2 = findf(u2);        if(u1 != u2) f[u1] = u2;    }    for(int i = 1;i <= n;i++){        r = findf(i);        temp.v = v[i];        temp.w = w[i];        itm[r].push_back(temp);        if(!vis[r]){            vis[r] = true;            cnt++;            tran[cnt] = r;        }    }    for(int i = 1;i <= cnt;i++){        now = tran[i];        for(int j = c;j >= 0;j--){            for(int t = 0;t < itm[now].size();t++){                if(j >= itm[now][t].w)dp[j] = max(dp[j],dp[j-itm[now][t].w] + itm[now][t].v);            }        }    }    cout<<dp[c];    return 0;}