cf 383 div2 D

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
#define pii 3.141592654
#define INF 1000000007
#define N 1005
#define M 10
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define si(x) scanf("%d",&x)
#define sif(x) scanf("%lf",&x)
#define sil(x) scanf("%I64d",&x)
#define pi(x) printf("%d\n",x)
#define pis(x) printf("%d ",x)
#define cpi(x) printf("Case %d: ",x)
#define pil(x) printf("%I64d\n",x)
#define rep(i,n,m) for(int i = n; i< m; i++)
#define reps(i,n,m) for(int i = n; i >= m; i--)
#define lft(x) x*2
#define rgt(x) x*2+1

int n,m,x,y,cmp,mark[N];
vector<int>ad[N];
int weight[N],w,allw[N],allb[N],nxt[N];
pair<int,int>pa[N];
ll beauty[N],dp[N][N];

void go(int u)
{
    mark[u] = cmp;
    allw[cmp] += weight[u];
    allb[cmp] += beauty[u];


    rep(i,0,ad[u].size()){
        int v = ad[u][i];
        if(!mark[v]){
            go(v);
        }
    }
}

ll go1(int pos,int tot)
{
    if(tot > w) return -1e12;
    if(pos > n) return 0;

    ll &ret = dp[pos][tot];
    if(ret != -1) return ret;

    ret = 0;

    int p = nxt[pos];
    ll a = 0;
    rep(i,pos,p){
        //two options
        //ami ai component er sb nite pari or akta niye next component a jete pari
        a = max(a,beauty[pa[i].S] + go1(nxt[i],tot+weight[pa[i].S]));
    }
    ll b = go1(nxt[pos],tot);
    ll c = allb[pa[pos].F] + go1(nxt[pos],tot+allw[pa[pos].F]);

    return ret = max(a,max(b,c));
}

int main()
{
    memset(dp,-1,sizeof(dp));
    si(n);si(m);si(w);
    rep(i,1,n+1) si(weight[i]);
    rep(i,1,n+1) sil(beauty[i]);

    rep(i,0,m){
        si(x);si(y);
        ad[x].pb(y);
        ad[y].pb(x);
    }
    cmp = 0;
    rep(i,1,n+1){
        if(!mark[i]){
            cmp++;
            go(i);
        }
    }


    rep(i,1,n+1){
        pa[i].F = mark[i];
        pa[i].S = i;
    }

    sort(pa+1,pa+n+1);
    int u = n + 1,y = pa[n].F;
    //this nxt array for finding efficiently next component's start index to escape time limit
    reps(i,n,1){
        if(y == pa[i].F){
            nxt[i] = u;
        }
        else{
            u = i + 1;
            y = pa[i].F;
            nxt[i] = u;
        }
    }

    ll ans = go1(1,0);

    pil(ans);


    return 0;
}