#include <bits/stdc++.h>
using namespace std;
using vi = vector<long long>;
template <typename T>
std::istream& operator>>(std::istream& input, std::pair<T, T>& data) {
  input >> data.first >> data.second;
  return input;
}
template <typename T>
std::istream& operator>>(std::istream& input, std::vector<T>& data) {
  for (T& first : data) input >> first;
  return input;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const pair<T, T>& data) {
  output << "(" << data.first << "," << data.second << ")";
  return output;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const std::vector<T>& data) {
  for (const T& first : data) output << first << " ";
  return output;
}
std::ostream& operator<<(std::ostream& output, const __int128& first) {
  __int128 n = first;
  if (n == 0) {
    output << "0";
    return output;
  }
  if (n < 0) {
    n = -n;
    output << "-";
  }
  string s;
  while (n) {
    s += '0' + (n % 10);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  cout << s;
  return output;
}
long long div_up(long long a, long long b) {
  return a / b + ((a ^ b) > 0 && a % b);
}
long long div_down(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
long long math_mod(long long a, long long b) { return a - b * div_down(a, b); }
template <class T>
using V = vector<T>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    tie(a, b) = make_pair(b, a % b);
  }
  return a;
}
long long Bit(long long mask, long long bit) { return (mask >> bit) & 1; }
const long long INF = 1e9;
struct Dinic {
  struct edge {
    long long to, flow, cap;
  };
  const static long long N = 20000;
  vector<edge> e;
  vector<long long> g[N + 7];
  long long dp[N + 7];
  long long ptr[N + 7];
  void clear() {
    for (long long i = 0; i < N + 7; i++) g[i].clear();
    e.clear();
  }
  void addEdge(long long a, long long b, long long cap) {
    g[a].push_back(e.size());
    e.push_back({b, 0, cap});
    g[b].push_back(e.size());
    e.push_back({a, 0, 0});
  }
  long long minFlow, start, finish;
  bool bfs() {
    for (long long i = 0; i < N; i++) dp[i] = -1;
    dp[start] = 0;
    vector<long long> st;
    long long uk = 0;
    st.push_back(start);
    while (uk < st.size()) {
      long long v = st[uk++];
      for (long long to : g[v]) {
        auto ed = e[to];
        if (ed.cap - ed.flow >= minFlow && dp[ed.to] == -1) {
          dp[ed.to] = dp[v] + 1;
          st.push_back(ed.to);
        }
      }
    }
    return dp[finish] != -1;
  }
  long long dfs(long long v, long long flow) {
    if (v == finish) return flow;
    for (; ptr[v] < g[v].size(); ptr[v]++) {
      long long to = g[v][ptr[v]];
      edge ed = e[to];
      if (ed.cap - ed.flow >= minFlow && dp[ed.to] == dp[v] + 1) {
        long long add = dfs(ed.to, min(flow, ed.cap - ed.flow));
        if (add) {
          e[to].flow += add;
          e[to ^ 1].flow -= add;
          return add;
        }
      }
    }
    return 0;
  }
  long long dinic(long long start, long long finish) {
    Dinic::start = start;
    Dinic::finish = finish;
    long long flow = 0;
    for (minFlow = (1ll << 30); minFlow; minFlow >>= 1) {
      while (bfs()) {
        for (long long i = 0; i < N; i++) ptr[i] = 0;
        while (long long now = dfs(start, (long long)2e9 + 7)) flow += now;
      }
    }
    return flow;
  }
} dinic;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, g;
  cin >> n >> m >> g;
  vi t(n + 1);
  long long S = 0, T = dinic.N - 1;
  for (long long i = (1); i < (n + 1); ++i) {
    cin >> t[i];
  }
  vi v(n + 1);
  for (long long i = (1); i < (n + 1); ++i) {
    cin >> v[i];
  }
  for (long long i = (1); i < (n + 1); ++i) {
    if (t[i]) {
      dinic.addEdge(i, T, v[i]);
    } else {
      dinic.addEdge(S, i, v[i]);
    }
  }
  long long ans = 0, ptr = n + 1;
  for (long long _ = (0); _ < (m); ++_) {
    long long want;
    cin >> want;
    long long cost, k;
    cin >> cost >> k;
    vi who(k);
    cin >> who;
    ans += cost;
    bool fri;
    cin >> fri;
    if (fri) {
      cost += g;
    }
    if (want) {
      for (auto& i : who) {
        dinic.addEdge(i, ptr, INF);
      }
      dinic.addEdge(ptr, T, cost);
    } else {
      for (auto& i : who) {
        dinic.addEdge(ptr, i, INF);
      }
      dinic.addEdge(S, ptr, cost);
    }
    ptr++;
  }
  cout << ans - dinic.dinic(S, T) << '\n';
}

### Prompt

Create a solution in CPP for the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using vi = vector<long long>;
template <typename T>
std::istream& operator>>(std::istream& input, std::pair<T, T>& data) {
  input >> data.first >> data.second;
  return input;
}
template <typename T>
std::istream& operator>>(std::istream& input, std::vector<T>& data) {
  for (T& first : data) input >> first;
  return input;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const pair<T, T>& data) {
  output << "(" << data.first << "," << data.second << ")";
  return output;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const std::vector<T>& data) {
  for (const T& first : data) output << first << " ";
  return output;
}
std::ostream& operator<<(std::ostream& output, const __int128& first) {
  __int128 n = first;
  if (n == 0) {
    output << "0";
    return output;
  }
  if (n < 0) {
    n = -n;
    output << "-";
  }
  string s;
  while (n) {
    s += '0' + (n % 10);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  cout << s;
  return output;
}
long long div_up(long long a, long long b) {
  return a / b + ((a ^ b) > 0 && a % b);
}
long long div_down(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
long long math_mod(long long a, long long b) { return a - b * div_down(a, b); }
template <class T>
using V = vector<T>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    tie(a, b) = make_pair(b, a % b);
  }
  return a;
}
long long Bit(long long mask, long long bit) { return (mask >> bit) & 1; }
const long long INF = 1e9;
struct Dinic {
  struct edge {
    long long to, flow, cap;
  };
  const static long long N = 20000;
  vector<edge> e;
  vector<long long> g[N + 7];
  long long dp[N + 7];
  long long ptr[N + 7];
  void clear() {
    for (long long i = 0; i < N + 7; i++) g[i].clear();
    e.clear();
  }
  void addEdge(long long a, long long b, long long cap) {
    g[a].push_back(e.size());
    e.push_back({b, 0, cap});
    g[b].push_back(e.size());
    e.push_back({a, 0, 0});
  }
  long long minFlow, start, finish;
  bool bfs() {
    for (long long i = 0; i < N; i++) dp[i] = -1;
    dp[start] = 0;
    vector<long long> st;
    long long uk = 0;
    st.push_back(start);
    while (uk < st.size()) {
      long long v = st[uk++];
      for (long long to : g[v]) {
        auto ed = e[to];
        if (ed.cap - ed.flow >= minFlow && dp[ed.to] == -1) {
          dp[ed.to] = dp[v] + 1;
          st.push_back(ed.to);
        }
      }
    }
    return dp[finish] != -1;
  }
  long long dfs(long long v, long long flow) {
    if (v == finish) return flow;
    for (; ptr[v] < g[v].size(); ptr[v]++) {
      long long to = g[v][ptr[v]];
      edge ed = e[to];
      if (ed.cap - ed.flow >= minFlow && dp[ed.to] == dp[v] + 1) {
        long long add = dfs(ed.to, min(flow, ed.cap - ed.flow));
        if (add) {
          e[to].flow += add;
          e[to ^ 1].flow -= add;
          return add;
        }
      }
    }
    return 0;
  }
  long long dinic(long long start, long long finish) {
    Dinic::start = start;
    Dinic::finish = finish;
    long long flow = 0;
    for (minFlow = (1ll << 30); minFlow; minFlow >>= 1) {
      while (bfs()) {
        for (long long i = 0; i < N; i++) ptr[i] = 0;
        while (long long now = dfs(start, (long long)2e9 + 7)) flow += now;
      }
    }
    return flow;
  }
} dinic;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, g;
  cin >> n >> m >> g;
  vi t(n + 1);
  long long S = 0, T = dinic.N - 1;
  for (long long i = (1); i < (n + 1); ++i) {
    cin >> t[i];
  }
  vi v(n + 1);
  for (long long i = (1); i < (n + 1); ++i) {
    cin >> v[i];
  }
  for (long long i = (1); i < (n + 1); ++i) {
    if (t[i]) {
      dinic.addEdge(i, T, v[i]);
    } else {
      dinic.addEdge(S, i, v[i]);
    }
  }
  long long ans = 0, ptr = n + 1;
  for (long long _ = (0); _ < (m); ++_) {
    long long want;
    cin >> want;
    long long cost, k;
    cin >> cost >> k;
    vi who(k);
    cin >> who;
    ans += cost;
    bool fri;
    cin >> fri;
    if (fri) {
      cost += g;
    }
    if (want) {
      for (auto& i : who) {
        dinic.addEdge(i, ptr, INF);
      }
      dinic.addEdge(ptr, T, cost);
    } else {
      for (auto& i : who) {
        dinic.addEdge(ptr, i, INF);
      }
      dinic.addEdge(S, ptr, cost);
    }
    ptr++;
  }
  cout << ans - dinic.dinic(S, T) << '\n';
}

```