Just to remind, girls in Arpa's land are really nice.

Mehrdad wants to invite some Hoses to the palace for a dancing party. Each Hos has some weight wi and some beauty bi. Also each Hos may have some friends. Hoses are divided in some friendship groups. Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, ..., ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

<image>

Arpa allowed to use the amphitheater of palace to Mehrdad for this party. Arpa's amphitheater can hold at most w weight on it. 

Mehrdad is so greedy that he wants to invite some Hoses such that sum of their weights is not greater than w and sum of their beauties is as large as possible. Along with that, from each friendship group he can either invite all Hoses, or no more than one. Otherwise, some Hoses will be hurt. Find for Mehrdad the maximum possible total beauty of Hoses he can invite so that no one gets hurt and the total weight doesn't exceed w.

Input

The first line contains integers n, m and w (1 ≤ n ≤ 1000, <image>, 1 ≤ w ≤ 1000) — the number of Hoses, the number of pair of friends and the maximum total weight of those who are invited.

The second line contains n integers w1, w2, ..., wn (1 ≤ wi ≤ 1000) — the weights of the Hoses.

The third line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 106) — the beauties of the Hoses.

The next m lines contain pairs of friends, the i-th of them contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi), meaning that Hoses xi and yi are friends. Note that friendship is bidirectional. All pairs (xi, yi) are distinct.

Output

Print the maximum possible total beauty of Hoses Mehrdad can invite so that no one gets hurt and the total weight doesn't exceed w.

Examples

Input

3 1 5
3 2 5
2 4 2
1 2


Output

6


Input

4 2 11
2 4 6 6
6 4 2 1
1 2
2 3


Output

7

Note

In the first sample there are two friendship groups: Hoses {1, 2} and Hos {3}. The best way is to choose all of Hoses in the first group, sum of their weights is equal to 5 and sum of their beauty is 6.

In the second sample there are two friendship groups: Hoses {1, 2, 3} and Hos {4}. Mehrdad can't invite all the Hoses from the first group because their total weight is 12 > 11, thus the best way is to choose the first Hos from the first group and the only one from the second group. The total weight will be 8, and the total beauty will be 7.










import java.io.*;
import java.util.*;
import java.math.BigInteger; 
import java.lang.*;





public class Main {
    
    
    
    
   static class sort implements Comparator<int[]>
   {
        public int compare(int[] a,int[] b)
        {
            
            return -b[0]+a[0];
        }
   }
   static class sort1 implements Comparator<long[]>
   {
        public int compare(long[] a,long[] b)
        {
            
          long c = -(a[0]-a[1]) + (b[0]-b[1]);

          if(c==0l) return 0;
          if(c>0l) return 1;
          return -1;
        }
   }
   static class sort5 implements Comparator<long[]>
   {
        public int compare(long[] a,long[] b)
        {
            
           double d1,d2;
           d1 = (a[0]+0.00)/(a[1]+0.00);
           d2 = (b[0]+0.00)/(b[1]+0.00);
           //int v = Double.comapre(d2,d1);
           double eph = 0.000000000000001;
           double d = (d2-d1);
          // pr(d1+" "+d2);
           if(d>eph) return 1;
           else if(d<eph) return -1;
           if(a[1]>b[1]) return 1;
           else if(b[1]>a[1]) return -1;
           return 0;
        }
   }
   static class sort11 implements Comparator<double[]>
   {
        public int compare(double[] a,double[] b)
        {
            //if(a[0] == b[0]) return a[1]-b[1];
           if(a[1] < b[1]) return -1;
           else if(a[1] > b[1]) return 1;
           return 0;
        }
   }
   public static String[] F(BufferedReader bf) throws Exception
    {
        return (bf.readLine().split(" "));
    }
    
   public static void pr(PrintWriter out,Object o)
   {
      
    out.println(o.toString());//out.flush();
    
   }
   public static void prW(PrintWriter out,Object o)
   {
      
    out.print(o.toString());//out.flush();
    
   }
   public static int intIn(String st)
   {
      return Integer.parseInt(st);
   }
   
   
    
    public static void pr(Object o)
    {
        System.out.println(o.toString());
    }
    public static void prW(Object o)
    {
        System.out.print(o.toString());
    }
    
   
    public static int inInt(String s)
    {
        return Integer.parseInt(s);
    }
    public static long in(String s)
    {
        return Long.parseLong(s);
    }
 
 
    static int[] toIntArray(String[] m) 
    { 
        int[] p=new int[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= inInt(m[o]);
        }
        return p;
    }
    static double[] toDArray(String[] m) 
    { 
        double[] p=new double[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= Double.parseDouble(m[o]);
        }
        return p;
    }
    static long[] toLArray(String[] m) 
    { 
       long[] p=new long[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= in(m[o]);
        }
        return p;
    }
   
     static long gcd(long a, long b)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b); 
        }
     
        static long pow(long x, long y, long p)
      {
        if(y == 0) return 1l;
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0l; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
    
   
    static int nCr(int n, int r, int p)
    {
        if (r > n - r)
            r = n - r;
 
        // The array C is going to store last
        // row of pascal triangle at the end.
        // And last entry of last row is nCr
        int C[] = new int[r + 1];
 
        C[0] = 1; // Top row of Pascal Triangle
 
        // One by constructs remaining rows of Pascal
        // Triangle from top to bottom
        for (int i = 1; i <= n; i++) {
 
            // Fill entries of current row using previous
            // row values
            for (int j = Math.min(i, r); j > 0; j--)
 
                // nCj = (n-1)Cj + (n-1)C(j-1);
                C[j] = (C[j] + C[j - 1]) % p;
        }
        return C[r];
    }
    // F(o,-1,tm,vis,par,o,mat);
   public static int log(int x)
   {
       boolean bol = true;

       if(((x-1)&x) == 0) bol=false;

       int c=0;
       while(x > 0)
       {
        x=(x/2);
        c++;
       }

       if(!bol) c--;
       return c;

   }

   
   static class sor implements Comparator<long[]>
   {
      public int compare(long[] a,long[] b)
      {
         if(a[0] == b[0])
         {
            if(a[1] < b[1]) return -1;
            return 1;
         }
         if(a[0] > b[0]) return 1;
         return -1;
      }
   }


    static long ncr(int n, int r)
    {
 
        // p holds the value of n*(n-1)*(n-2)...,
        // k holds the_ value of r*(r-1)...
        long p = 1, k = 1;
        if(n<r) return 0l;
 
        // C(n, r) == C(n, n-r),
        // choosing the smaller value
        if (n - r < r) {
            r = n - r;
        }
 
        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
 
                // gcd of p, k
                long m = __gcd(p, k);
 
                // dividing by gcd, to simplify
                // product division by their gcd
                // saves from the overflow
                p /= m;
                k /= m;
 
                n--;
                r--;
            }
 
            // k should be simplified to 1
            // as C(n, r) is a natural number
            // (denominator should be 1 ) .
        }
        else {
            p = 1;
        }
 
        // if our approach is correct p = ans and k =1
        return p;
    }
       static class DSU {
    
    int[] p;int[] sz;int op;int c;;
    int[] last;
    public void G(int n)
    {
        last=new int[n];
        p=new int[n];
        sz=new int[n];c=n;
        op=n;
        for(int h=0;h<n;h++)
        {
            sz[h]=1;p[h]=h;
            last[h]=h;
        }
    }
    public int find(int x)
    {
        int y=x;
        while(x!=p[x]) x=p[x];
        while(y!=p[y])
        {
            int tem=p[y];
            p[y]=x;y=tem;
        }
        return p[y];
    }
    public void union(int a,int b)
    {
        int x,y;
        x=find(a);y=find(b);
        if(x==y) return;
        if(sz[x]>sz[y])
        {
            p[y] = x;
            sz[x]+=sz[y];
            last[x]=Math.max(last[x],last[y]);
        }
        else
        {
            p[x]=y;sz[y]+=sz[x];
            last[y]=Math.max(last[y],last[x]);
        }
        c--;
        
    }}
    static long __gcd(long n1, long n2)
    {

        if(n1==0l) return n2;
        if(n2==0l) return n1;
        if(n1==1l || n2==1l) return 1l;
       // long gcd = 1;
        if(n1 == n2)  return n1;
        if(n1>n2) return __gcd(n1%n2,n2);
        return __gcd(n1,n2%n1);
        
    }
    static long big = -1000000000000000l;
    static long max=big*100l;
   public static void F(int i,List<List<Integer>> list,List<int[]> arr,int in,boolean[] vis)
   {
      vis[i] = true;
      arr.add(new int[]{i,in});
      for(int y : list.get(i))
      {
            if(!vis[y])
            {
                  F(y,list,arr,in,vis);
            }
      }



   }
   static List<int[]> arr;
   static int[] cost;
   static int[] opo;
   public static long F(int i,int w,Long[][] dp)
   {
      int n=arr.size();
      if(i>=(n))
      {
            if(w>=0) return 0l;
            return -1000000000000l;
      }
      if(w<0) return -1000000000000l;
      if(dp[i][w] != null)  return dp[i][w];

      long res = F(i+1,w,dp);
      int wt = cost[arr.get(i)[0]];
      res = Math.max(res,F(arr.get(i)[1],w-wt,dp)+opo[arr.get(i)[0]]+0l);
      long c = 0l;wt=0;
      int[] p  = arr.get(i);
      if((i>0 && arr.get(i-1)[1] !=p[1]) || i==0)
      {
            for(int j=i;j<arr.get(i)[1];j++)
            {
                  wt += (cost[arr.get(j)[0]]);
                  c += (opo[arr.get(j)[0]]);
            }
            res = Math.max(res,F(arr.get(i)[1],w-wt,dp)+c);
      }

      dp[i][w] = res;
      return res;
   }
    public static void main (String[] args) throws Exception {
        
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);;;
        
        //int[] map=new int[1000001];
      
       int yy=1;//inInt(bf.readLine());
       


        //Long[][][] dp = new Long[100001][101][2];
        for(int w=0;w<yy;w++)
        {
             //String str = bf.readLine();
          out.flush();
         
            String[] xlp = bf.readLine().split(" ");;;;;;
            //String st = bf.readLine();
        int n;//boolean bol=false;
           int  m;//long a,b,c;
           int l;
           //int  k;//pr(out,"vbc");
         n=inInt(xlp[0]);m=inInt(xlp[1]);int p=inInt(xlp[2]);//int tb=inInt(xlp[3]);k=inInt(xlp[4]);
        //l=inInt(xlp[2]); k =inInt(xlp[3]);
         
         int[] a1,a2;
         a1 = toIntArray(F(bf));
         a2=toIntArray(F(bf));
         cost = a1;







         List<List<Integer>> list=new ArrayList<>();


         for(int i=0;i<n;i++)
         {
            list.add(new ArrayList<>());
         }
         opo=a2;
         for(int i=0;i<m;i++)
         {
            int[] tem=toIntArray(F(bf));

            tem[0]--;
            list.get(tem[0]).add(tem[1]-1);
            list.get(tem[1]-1).add(tem[0]);
         }
         int in=0;
         boolean[] vis=new boolean[n];
        arr=new ArrayList<>();
         for(int i=0;i<n;i++)
         {
            if(!vis[i])
            {
                  F(i,list,arr,in,vis);
                  in++;
            }
         }
        
            int last=-1;
           int index=arr.size()+1;
           for(int i=n-1;i>=0;i--)
           {
               int[] tp = arr.get(i);
               if(tp[1] != last)
               {
                  index=i+1;
                  last = tp[1];
               }
               tp[1] = index;
           }
            //for(int[] ip : arr) pr(out,ip[0]+" "+ip[1]);

        long res = F(0,p,new Long[n][p+1]);
         ///pr(out,arr);

  pr(out,res);






         

         





        

          




      

         
         
         



         
         
   }
    out.close();
   bf.close();
}}


/*
98
17 17 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 90 90 90 90 90 90 90 90 90 90 90 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 95 95 95 95 95 97 98 98



Kickstart
 String rp;
            rp = "Case #"+(w+1)+": "+(n-ans)+" ";
static int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};

static class SegmentTreeRMQ 
    { 
    int st[]; 
    int minVal(int x, int y) { 
        return (x > y) ? x : y; 
    } 
  
    
    int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
    
    int RMQUtil(int ss, int se, int qs, int qe, int index) 
    { 
        
        if (qs <= ss && qe >= se) 
            return st[index]; 
  
        // If segment of this node is outside the given range 
        if (se < qs || ss > qe) 
            return Integer.MIN_VALUE; 
  
        // If a part of this segment overlaps with the given range 
        int mid = getMid(ss, se); 
        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
    } 
  
    // Return minimum of elements in range from index qs (query 
    // start) to qe (query end).  It mainly uses RMQUtil() 
    int RMQ(int n, int qs, int qe) 
    { 
        // Check for erroneous input values 
        
  
        return RMQUtil(0, n - 1, qs, qe, 0); 
    } 
  
    // A recursive function that constructs Segment Tree for 
    // array[ss..se]. si is index of current node in segment tree st 
    int constructSTUtil(int arr[], int ss, int se, int si) 
    { 
        // If there is one element in array, store it in current 
        //  node of segment tree and return 
        if (ss == se) { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
  
        // If there are more than one elements, then recur for left and 
        // right subtrees and store the minimum of two values in this node 
        int mid = getMid(ss, se); 
        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
                constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
        return st[si]; 
    } 
  
    
    void con(int arr[]) 
    { 
        // Allocate memory for segment tree 
  
        //Height of segment tree 
        int n = (arr.length);
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
  
        //Maximum size of segment tree 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
        st = new int[max_size]; // allocate memory 
  
        // Fill the allocated memory st 
        constructSTUtil(arr, 0, n - 1, 0); 
    }
    }
     static class DSU {
    
    int[] p;int[] sz;int op;int c;;
    int[] last;
    public void G(int n)
    {
        last=new int[n];
        p=new int[n];
        sz=new int[n];c=n;
        op=n;
        for(int h=0;h<n;h++)
        {
            sz[h]=1;p[h]=h;
            last[h]=h;
        }
    }
    public int find(int x)
    {
        int y=x;
        while(x!=p[x]) x=p[x];
        while(y!=p[y])
        {
            int tem=p[y];
            p[y]=x;y=tem;
        }
        return p[y];
    }
    public void union(int a,int b)
    {
        int x,y;
        x=find(a);y=find(b);
        if(x==y) return;
        if(sz[x]>sz[y])
        {
            p[y] = x;
            sz[x]+=sz[y];
            last[x]=Math.max(last[x],last[y]);
        }
        else
        {
            p[x]=y;sz[y]+=sz[x];
            last[y]=Math.max(last[y],last[x]);
        }
        c--;
        
    }}

    static long pow(long x, long y, long p)
      {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0l; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
      static long gcd(long a, long b)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b); 
        }
        static int gcd(int a, int b,int o)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b,o); 
        }

Geometric median

public static double F(double[] x,double[] w)
    {
        double d1,d2;
        double S=0.00;
        for(double dp : w) S += dp;
        int k = 0;
        double sum = S - w[0]; // sum is the total weight of all `x[i] > x[k]`

        while(sum > S/2)
        {
            ++k;
            sum -= w[k];
        }
        d1=x[k];
        return d1;
        k = w.length-1;
       sum = S - w[k]; // sum is the total weight of all `x[i] > x[k]`

        while(sum > S/2)
        {
            --k;
            sum -= w[k];
        }
        d2=x[k];
        return new double[]{d1,d2};
    }
*/

















