Problem: SmallR is a biologist. Her latest research finding is how to change the sex of dogs. In other words, she can change female dogs into male dogs and vice versa.

She is going to demonstrate this technique. Now SmallR has n dogs, the costs of each dog's change may be different. The dogs are numbered from 1 to n. The cost of change for dog i is vi RMB. By the way, this technique needs a kind of medicine which can be valid for only one day. So the experiment should be taken in one day and each dog can be changed at most once.

This experiment has aroused extensive attention from all sectors of society. There are m rich folks which are suspicious of this experiment. They all want to bet with SmallR forcibly. If SmallR succeeds, the i-th rich folk will pay SmallR wi RMB. But it's strange that they have a special method to determine whether SmallR succeeds. For i-th rich folk, in advance, he will appoint certain ki dogs and certain one gender. He will think SmallR succeeds if and only if on some day the ki appointed dogs are all of the appointed gender. Otherwise, he will think SmallR fails.

If SmallR can't satisfy some folk that isn't her friend, she need not pay him, but if someone she can't satisfy is her good friend, she must pay g RMB to him as apologies for her fail.

Then, SmallR hope to acquire money as much as possible by this experiment. Please figure out the maximum money SmallR can acquire. By the way, it is possible that she can't obtain any money, even will lose money. Then, please give out the minimum money she should lose.

Input

The first line contains three integers n, m, g (1 ≤ n ≤ 104, 0 ≤ m ≤ 2000, 0 ≤ g ≤ 104). The second line contains n integers, each is 0 or 1, the sex of each dog, 0 represent the female and 1 represent the male. The third line contains n integers v1, v2, ..., vn (0 ≤ vi ≤ 104).

Each of the next m lines describes a rich folk. On the i-th line the first number is the appointed sex of i-th folk (0 or 1), the next two integers are wi and ki (0 ≤ wi ≤ 104, 1 ≤ ki ≤ 10), next ki distinct integers are the indexes of appointed dogs (each index is between 1 and n). The last number of this line represents whether i-th folk is SmallR's good friend (0 — no or 1 — yes).

Output

Print a single integer, the maximum money SmallR can gain. Note that the integer is negative if SmallR will lose money. 

Examples

Input

5 5 9
0 1 1 1 0
1 8 6 2 3
0 7 3 3 2 1 1
1 8 1 5 1
1 0 3 2 1 4 1
0 8 3 4 2 1 0
1 7 2 4 1 1


Output

2


Input

5 5 8
1 0 1 1 1
6 5 4 2 8
0 6 3 2 3 4 0
0 8 3 3 2 4 0
0 0 3 3 4 1 1
0 10 3 4 3 1 1
0 4 3 3 4 1 1


Output

16

Solution (in JAVA):

Solution:
// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*; 
 
// Please name your class Main
public class Main {
	
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
 
    static int read() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
    static String readString() throws IOException {
        in.nextToken();
        return in.sval;
	}
	
	
	public static void main (String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		//InputReader in = new InputReader(System.in);
 
		
		int n=in.nextInt();
		int m=in.nextInt();
		int g=in.nextInt();
		int total=0;
		int A[]=new int[n];
		int V[]=new int[n];
		for(int i=0;i<n;i++){
			A[i]=in.nextInt();
		}
		
		for(int i=0;i<n;i++){
			V[i]=in.nextInt();
		}
	
		Solution s=new Solution();
		s.solution(m,A,V,g,total,out,in);
		out.flush();
	}
 
}
 
class Solution{
	//constant variable
	final int MAX=Integer.MAX_VALUE;
	final int MIN=Integer.MIN_VALUE;
	//Set<Integer>adjecent[];
	//////////////////////////////

	//Map<Integer,List<int[]>>map=new HashMap<>();
	
	List<int[]>map[]=new ArrayList[20500];
	
	int INF=1000000000;
	int S=10002;
	int T=10003;
	public void solution(int m,int A[],int V[],int g,int total,PrintWriter out,Scanner in){
		List<Edge>[] graph = createGraph(20500);
		int n=A.length;
		
		for(int i=1;i<=A.length;i++){
			if(A[i-1]==0){
				addEdge(graph, S, i, V[i-1]);
			}else{
				addEdge(graph, i, T, V[i-1]);
				
			}
		}
		
		for(int i=0;i<m;i++){
			int per=i+1+T;
			
			int first=in.nextInt();
			
			int w=in.nextInt();
			int k=in.nextInt();
			total+=w;

			for(int j=0;j<k;j++){
				int dogIndex=in.nextInt();
				if(first==0){
					if(true){						
						addEdge(graph, per, dogIndex, INF);
					}
				}else{
					if(true){
						addEdge(graph, dogIndex, per, INF);
					}
				}
			}
			
			int friend=in.nextInt();
			if(friend==1)w+=g;
			
			if(first==0){
				addEdge(graph, S, per, w);
			}else{
				addEdge(graph, per, T, w);
			}
		}
		
		int flow=maxFlow(graph,S,T);
		out.println((total-flow)+"");
	}
	
	/*public int  maxflow(){
		int N=21000;
		int flow=0;
		while(true){
			int f=MAX;
            int path[]=new int[N];
            Arrays.fill(path,-1);
            Queue<Integer>q=new LinkedList<>();
            q.add(S);
            boolean visit[]=new boolean[N];
            visit[S]=true;
            while(q.size()!=0){
                int parent=q.poll();
                if(parent==T)break;
				List<int[]>childs=map[parent];
                for(int i=0;i<childs.size();i++){
                    int pair[]=childs.get(i);
					int c=pair[0];
					if(pair[1]>0&&!visit[c]){
						f=Math.min(f,pair[1]);
                        visit[c]=true;
                        path[c]=parent;
                        q.add(c);
                    }
                }
            }
            if(path[T]==-1||f==MAX)break;
            int cur=T;
            while(true){
                int parent=path[cur];
				List<int[]>l1=map[parent];
				for(int pair[]:l1){
					if(pair[0]==cur)pair[1]-=f;
				}
				
				List<int[]>l2=map[cur];
				for(int pair[]:l2){
					if(pair[0]==parent)pair[1]+=f;
				}
                cur=parent;
                if(cur==S)break;
            }
			
            flow+=f;
        }
		return flow;
	}*/
	
 
 
	
	
	
	static class Edge {
		int t, rev, cap, f;

		public Edge(int t, int rev, int cap) {
		  this.t = t;
		  this.rev = rev;
		  this.cap = cap;
		}
	  }

	  public static List<Edge>[] createGraph(int nodes) {
		List<Edge>[] graph = new List[nodes];
		for (int i = 0; i < nodes; i++)
		  graph[i] = new ArrayList<>();
		return graph;
	  }

	  public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
		graph[s].add(new Edge(t, graph[t].size(), cap));
		graph[t].add(new Edge(s, graph[s].size() - 1, 0));
	  }

	  static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
		Arrays.fill(dist, -1);
		dist[src] = 0;
		int[] Q = new int[graph.length];
		int sizeQ = 0;
		Q[sizeQ++] = src;
		for (int i = 0; i < sizeQ; i++) {
		  int u = Q[i];
		  for (Edge e : graph[u]) {
			if (dist[e.t] < 0 && e.f < e.cap) {
			  dist[e.t] = dist[u] + 1;
			  Q[sizeQ++] = e.t;
			}
		  }
		}
		return dist[dest] >= 0;
	  }

	  static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
		if (u == dest)
		  return f;
		for (; ptr[u] < graph[u].size(); ++ptr[u]) {
		  Edge e = graph[u].get(ptr[u]);
		  if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
			int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
			if (df > 0) {
			  e.f += df;
			  graph[e.t].get(e.rev).f -= df;
			  return df;
			}
		  }
		}
		return 0;
	  }

	  public static int maxFlow(List<Edge>[] graph, int src, int dest) {
		int flow = 0;
		int[] dist = new int[graph.length];
		while (dinicBfs(graph, src, dest, dist)) {
		  int[] ptr = new int[graph.length];
		  while (true) {
			int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
			if (df == 0)
			  break;
			flow += df;
		  }
		}
		return flow;
	  }


	
	
	
	
	
	
	public void swap(int A[],int l,int r){
		int t=A[l];
		A[l]=A[r];
		A[r]=t;
	}
	
	
	public long C(long fact[],int i,int j){ // C(20,3)=20!/(17!*3!)
		// take   a/b     where a=20!  b=17!*3!
		if(j>i)return 0;
		if(j==0)return 1;
		long mod=998244353;
		long a=fact[i];
		long b=((fact[i-j]%mod)*(fact[j]%mod))%mod;
		BigInteger B= BigInteger.valueOf(b);
		long binverse=B.modInverse(BigInteger.valueOf(mod)).longValue();
		return ((a)*(binverse%mod))%mod;
	}
	
	 
	
	//map operation
	public void put(Map<Integer,Integer>map,int i){
		if(!map.containsKey(i))map.put(i,0);
		map.put(i,map.get(i)+1);
	}
	
	public void delete(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
 
 

	
 
	
 
 
	/*public void tarjan(int p,int r){
		if(cut)return;
		List<Integer>childs=adjecent[r];
		dis[r]=low[r]=time;
		time++;
		
		//core for tarjan
		int son=0;
		for(int c:childs){
			if(ban==c||c==p)continue;
			if(dis[c]==-1){
				son++;
				tarjan(r,c);
				low[r]=Math.min(low[r],low[c]);
				if((r==root&&son>1)||(low[c]>=dis[r]&&r!=root)){
					cut=true;
					return;
				}
			}else{
				if(c!=p){
					low[r]=Math.min(low[r],dis[c]);
				}
			}
		}
		
	}*/
	
	
 
	
	
		
	
	//helper function I would use
	public void remove(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
	
	
	
	public void ascii(String s){
		for(char c:s.toCharArray()){
			System.out.print((c-'a')+" ");
		}
		msg("");
	}
	
	public int flip(int i){
		if(i==0)return 1;
		else return 0;
	}
	
	public boolean[] primes(int n){
		boolean A[]=new boolean[n+1];
		for(int i=2;i<=n;i++){
			if(A[i]==false){
				for(int j=i+i;j<=n;j+=i){
					A[j]=true;
				}
			}
		}
		return A;
	}
	
	public void msg(String s){
		System.out.println(s);
	}
	
	public void msg1(String s){
		System.out.print(s);
	}
	
	public int[] kmpPre(String p){
		int pre[]=new int[p.length()];
		int l=0,r=1;
		while(r<p.length()){
			if(p.charAt(l)==p.charAt(r)){
				pre[r]=l+1;
				l++;r++;
			}else{
				if(l==0)r++;
				else l=pre[l-1];
			}
		}
		return pre;
	}
	
	public boolean isP(String s){
		int l=0,r=s.length()-1;
		while(l<r){
			if(s.charAt(l)!=s.charAt(r))return false;
			l++;r--;
		}
		return true;
	}
	
	public int find(int nums[],int x){//union find => find method
		if(nums[x]==x)return x;
		int root=find(nums,nums[x]);
		nums[x]=root;
		return root;
	}
	

	
	public int get(int A[],int i){
		if(i<0||i>=A.length)return 0;
		return A[i];
	}
	public int[] copy1(int A[]){
		int a[]=new int[A.length];
		for(int i=0;i<a.length;i++)a[i]=A[i];
		return a;
	}
	
	public int[] copy2(int A[]){
		int a[]=new int[A.length];
		for(int i=0;i<a.length;i++)a[i]=A[i];
		return a;
	}
	
	
	public void print1(int A[]){
		for(long i:A)System.out.print(i+" ");
		System.out.println();
	}
	public void print2(long A[][]){
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				System.out.print(A[i][j]+" ");
			}System.out.println();
		}
	}
	
	public int min(int a,int b){
		return Math.min(a,b);
	}
	
	
	public int[][] matrixdp(int[][] grid) {
        if(grid.length==0)return new int[][]{};
        int res[][]=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                res[i][j]=grid[i][j]+get(res,i-1,j)+get(res,i,j-1)-get(res,i-1,j-1);
            }
        }
        return res;
    }
    
    public int get(int grid[][],int i,int j){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length)return 0;
        return grid[i][j];
    }
	
	public int[] suffixArray(String s){
		int n=s.length();
		Suffix A[]=new Suffix[n];
		
		for(int i=0;i<n;i++){
			A[i]=new Suffix(i,s.charAt(i)-'a',0);
		}
		
		for(int i=0;i<n;i++){
			if(i==n-1){
				A[i].next=-1;
			}else{
				A[i].next=A[i+1].rank;
			}
		}
		Arrays.sort(A);
		
		for(int len=4;len<A.length*2;len<<=1){
			int in[]=new int[A.length];
			int rank=0;
			int pre=A[0].rank;
			A[0].rank=rank;
			in[A[0].index]=0;
			for(int i=1;i<A.length;i++){//rank for the first two letter
				if(A[i].rank==pre&&A[i].next==A[i-1].next){
					pre=A[i].rank;
					A[i].rank=rank;
				}else{
					pre=A[i].rank;
					A[i].rank=++rank;
				}
				in[A[i].index]=i;
			}
			
			for(int i=0;i<A.length;i++){
				int next=A[i].index+len/2;
				if(next>=A.length){
					A[i].next=-1;
				}else{
					A[i].next=A[in[next]].rank;
				}
			}
			
			
			Arrays.sort(A);
		}
		
		
		int su[]=new int[A.length];
		for(int i=0;i<su.length;i++){
			su[i]=A[i].index;
		}
		return su;
	}
	
}
 
//suffix array Struct
class Suffix implements Comparable<Suffix>{
	int index;
	int rank;
	int next;
	public Suffix(int i,int rank,int next){
		this.index=i;
		this.rank=rank;
		this.next=next;
	}
	
	@Override
	public int compareTo(Suffix other) {
		if(this.rank==other.rank){
			return this.next-other.next;
		}
		return this.rank-other.rank;
	}
	
	public String toString(){
		return this.index+"   "+this.rank+"   "+this.next+"  ";
	}
}
 
 
 
class Wrapper implements Comparable<Wrapper>{
	int spf;int cnt;
	public Wrapper(int spf,int cnt){
		this.spf=spf;
		this.cnt=cnt;
	}
		
	@Override
	public int compareTo(Wrapper other) {
		return this.spf-other.spf;
	}
}
 
 
 
    class Node{//what the range would be for that particular node
		boolean state=false;
        int l=0,r=0;
		int ll=0,rr=0;
        public Node(boolean state){
            this.state=state;
        }
    }
	
	
	
	
	class Seg1{
			int A[];
			public Seg1(int A[]){
				this.A=A;
			}
			
			public void update(int left,int right,int val,int s,int e,int id){
				if(left<0||right<0||left>right)return;
				if(left==s&&right==e){
					
					A[id]+=val;
					return;
				}
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(left>=mid+1){
					update(left,right,val,mid+1,e,id*2+2);
				}else if(right<=mid){
					update(left,right,val,s,mid,id*2+1);
				}else{
					update(left,mid,val,s,mid,id*2+1);
					update(mid+1,right,val,mid+1,e,id*2+2);
				}
			}
			
			public int query(int i,int add,int s,int e,int id){
				
				if(s==e&&i==s){
					return A[id]+add;
				}
				
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(i>=mid+1){
					return query(i,A[id]+add,mid+1,e,id*2+2);
				}else{
					return query(i,A[id]+add,s,mid,id*2+1);
				}
			}
	}