#include <bits/stdc++.h>
namespace CoreLibrary {
class Reader {
 private:
  std::FILE* file;
  std::vector<char> buffer;
  char *pointer, *end;
  inline void read_file() {
    for (int i = 0;; ++i) {
      buffer.resize(buffer.size() + (1 << i));
      int t =
          std::fread(&buffer[0] + buffer.size() - (1 << i), 1, (1 << i), file);
      if (t != (1 << i)) {
        pointer = &buffer[0];
        end = pointer + buffer.size() - (1 << i) + t;
        break;
      }
    }
  }
  inline void read(char& a) { a = *pointer++; }
  inline void read(char* a) {
    ignore();
    while (pointer != end && !std::isspace(*pointer)) *a++ = *pointer++;
    *a = 0;
  }
  inline void read(int& a) {
    ignore();
    bool f = false;
    if (*pointer == '-') {
      f = true;
      ++pointer;
    }
    a = 0;
    while (pointer != end && std::isdigit(*pointer))
      a = a * 10 + *pointer++ - '0';
    if (f) a = -a;
  }
  inline void read(long long& a) {
    ignore();
    bool f = false;
    if (*pointer == '-') {
      f = true;
      ++pointer;
    }
    a = 0;
    while (pointer != end && std::isdigit(*pointer))
      a = a * 10 + *pointer++ - '0';
    if (f) a = -a;
  }
  inline void ignore() {
    while (pointer != end && std::isspace(*pointer)) ++pointer;
  }

 public:
  inline Reader(std::FILE* _file) : file(_file) { read_file(); }
  inline Reader(std::string _file) : file(std::fopen(_file.c_str(), "r")) {
    read_file();
  }
  inline ~Reader() { fclose(file); }
  template <class VALUE_TYPE>
  inline Reader& operator>>(VALUE_TYPE& a) {
    read(a);
    return *this;
  }
};
class Writer {
 private:
  std::FILE* file;
  std::vector<char> buffer;
  inline void write(char a) { buffer.push_back(a); }
  inline void write(const char* a) {
    while (*a) buffer.push_back(*a++);
  }
  inline void write(int a) {
    if (a < 0) {
      buffer.push_back('-');
      a = -a;
    }
    static char t[10];
    char* p = t;
    do {
      int b = a / 10;
      *p++ = a - b * 10 + '0';
      a = b;
    } while (a);
    while (p > t) buffer.push_back(*--p);
  }
  inline void write(long long a) {
    if (a < 0) {
      buffer.push_back('-');
      a = -a;
    }
    static char t[19];
    char* p = t;
    do {
      long long b = a / 10;
      *p++ = a - b * 10 + '0';
      a = b;
    } while (a);
    while (p > t) buffer.push_back(*--p);
  }

 public:
  inline Writer(std::FILE* _file) : file(_file) {}
  inline Writer(std::string _file) : file(std::fopen(_file.c_str(), "w")) {}
  inline ~Writer() {
    std::fwrite(&buffer[0], 1, buffer.size(), file);
    fclose(file);
  }
  template <class VALUE_TYPE>
  inline Writer& operator<<(VALUE_TYPE a) {
    write(a);
    return *this;
  }
};
template <class VALUE_TYPE>
inline bool MakeMax(VALUE_TYPE& a, const VALUE_TYPE& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class VALUE_TYPE>
inline bool MakeMin(VALUE_TYPE& a, const VALUE_TYPE& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class VALUE_TYPE>
inline VALUE_TYPE Abs(const VALUE_TYPE& a) {
  return a < VALUE_TYPE(0) ? -a : a;
}
}  // namespace CoreLibrary
namespace DataStructures {
template <class VALUE_TYPE, class COMPARER_TYPE>
class Set {
 private:
  struct node {
    inline node(const VALUE_TYPE& _value, node* _left, node* _right,
                node* _parent, const bool& _black, const int& _size,
                const int& _count)
        : value(_value),
          left(_left),
          right(_right),
          parent(_parent),
          black(_black),
          size(_size),
          count(_count) {}
    VALUE_TYPE value;
    node *left, *right, *parent;
    bool black;
    int size, count;
  } * root, *nil;
  inline void clear(node* x) {
    if (x != nil) {
      clear(x->left);
      clear(x->right);
      delete x;
    }
  }
  inline void left_rotate(node* x) {
    node* y = x->right;
    x->right = y->left;
    if (y->left != nil) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == nil)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else
      x->parent->right = y;
    y->left = x;
    x->parent = y;
    y->size = x->size;
    x->size = x->left->size + x->right->size + x->count;
  }
  inline void right_rotate(node* x) {
    node* y = x->left;
    x->left = y->right;
    if (y->right != nil) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == nil)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else
      x->parent->right = y;
    y->right = x;
    x->parent = y;
    y->size = x->size;
    x->size = x->left->size + x->right->size + x->count;
  }
  inline void insert_fixup(node* z) {
    while (!z->parent->black) {
      if (z->parent == z->parent->parent->left) {
        node* y = z->parent->parent->right;
        if (!y->black) {
          z->parent->black = true;
          y->black = true;
          (z = z->parent->parent)->black = false;
        } else {
          if (z == z->parent->right) left_rotate(z = z->parent);
          z->parent->black = true;
          z->parent->parent->black = false;
          right_rotate(z->parent->parent);
        }
      } else {
        node* y = z->parent->parent->left;
        if (!y->black) {
          z->parent->black = true;
          y->black = true;
          (z = z->parent->parent)->black = false;
        } else {
          if (z == z->parent->left) right_rotate(z = z->parent);
          z->parent->black = true;
          z->parent->parent->black = false;
          left_rotate(z->parent->parent);
        }
      }
    }
    root->black = true;
  }
  inline void erase(node* z) {
    node* y;
    if (z->left == nil || z->right == nil)
      y = z;
    else {
      y = z->right;
      while (y->left != nil) y = y->left;
      z->value = y->value;
      z->count = y->count;
      int t = y->count;
      y->count = 0;
      y = z->right;
      while (y->left != nil) {
        y->size -= t;
        y = y->left;
      }
    }
    node* x = y->left == nil ? y->right : y->left;
    x->parent = y->parent;
    if (y->parent == nil)
      root = x;
    else if (y == y->parent->left)
      y->parent->left = x;
    else
      y->parent->right = x;
    if (y->black) erase_fixup(x);
    delete y;
  }
  inline void erase_fixup(node* x) {
    while (x != root && x->black) {
      if (x == x->parent->left) {
        node* w = x->parent->right;
        if (!w->black) {
          w->black = true;
          x->parent->black = false;
          left_rotate(x->parent);
          w = x->parent->right;
        }
        if (w->left->black && w->right->black) {
          w->black = false;
          x = x->parent;
        } else {
          if (w->right->black) {
            w->left->black = true;
            w->black = false;
            right_rotate(w);
            w = x->parent->right;
          }
          w->black = x->parent->black;
          x->parent->black = true;
          w->right->black = true;
          left_rotate(x->parent);
          x = root;
        }
      } else {
        node* w = x->parent->left;
        if (!w->black) {
          w->black = true;
          x->parent->black = false;
          right_rotate(x->parent);
          w = x->parent->left;
        }
        if (w->left->black && w->right->black) {
          w->black = false;
          x = x->parent;
        } else {
          if (w->left->black) {
            w->right->black = true;
            w->black = false;
            left_rotate(w);
            w = x->parent->left;
          }
          w->black = x->parent->black;
          x->parent->black = true;
          w->left->black = true;
          right_rotate(x->parent);
          x = root;
        }
      }
    }
    x->black = true;
  }
  inline node* clone(node* x, node* y) {
    if (!x->count) return nil;
    node* z = new node(*x);
    z->left = clone(x->left, z);
    z->right = clone(x->right, z);
    z->parent = y;
    return z;
  }

 public:
  class Iterator {
   private:
    node* pointer;
    friend class Set;
    inline node* precursor(node* x) {
      if (x->left->count) {
        x = x->left;
        while (x->right->count) x = x->right;
        return x;
      } else {
        node* y = x->parent;
        while (y->count && x == y->left) {
          x = y;
          y = y->parent;
        }
        return y;
      }
    }
    inline node* successor(node* x) {
      if (x->right->count) {
        x = x->right;
        while (x->left->count) x = x->left;
        return x;
      } else {
        node* y = x->parent;
        while (y->count && x == y->right) {
          x = y;
          y = y->parent;
        }
        return y;
      }
    }

   public:
    inline Iterator(node* _pointer) : pointer(_pointer) {}
    inline ~Iterator() {}
    inline bool operator==(const Iterator& a) { return pointer == a.pointer; }
    inline bool operator!=(const Iterator& a) { return pointer != a.pointer; }
    inline VALUE_TYPE operator*() { return pointer->value; }
    inline VALUE_TYPE* operator->() { return &pointer->value; }
    inline Iterator& operator++() {
      pointer = successor(pointer);
      return *this;
    }
    inline Iterator operator++(int) {
      Iterator t = *this;
      pointer = successor(pointer);
      return t;
    }
    inline Iterator& operator--() {
      pointer = precursor(pointer);
      return *this;
    }
    inline Iterator operator--(int) {
      Iterator t = *this;
      pointer = precursor(pointer);
      return t;
    }
  };
  inline Set() { root = nil = new node(VALUE_TYPE(), 0, 0, 0, true, 0, 0); }
  inline Set(const Set& a) {
    nil = new node(*a.nil);
    root = clone(a.root, nil);
  }
  inline ~Set() {
    clear(root);
    delete nil;
  }
  inline Set& operator=(const Set& a) {
    clear(root);
    root = clone(a.root, nil);
    return *this;
  }
  Iterator Begin() {
    node* z = root;
    while (z != nil && z->left != nil) z = z->left;
    return Iterator(z);
  }
  Iterator ReverseBegin() {
    node* z = root;
    while (z != nil && z->right != nil) z = z->right;
    return Iterator(z);
  }
  Iterator End() { return Iterator(nil); }
  Iterator ReverseEnd() { return Iterator(nil); }
  inline void Clear() {
    clear(root);
    root = nil;
  }
  inline void Insert(const VALUE_TYPE& a) {
    node *y = nil, *x = root;
    while (x != nil) {
      y = x;
      ++x->size;
      if (COMPARER_TYPE()(a, x->value))
        x = x->left;
      else if (COMPARER_TYPE()(x->value, a))
        x = x->right;
      else {
        ++x->count;
        return;
      }
    }
    node* z = new node(a, nil, nil, y, false, 1, 1);
    if (y == nil)
      root = z;
    else if (COMPARER_TYPE()(z->value, y->value))
      y->left = z;
    else
      y->right = z;
    insert_fixup(z);
  }
  inline void Erase(const Iterator& a) {
    node* z = root;
    while (true) {
      z->size -= a.pointer->count;
      if (COMPARER_TYPE()(a.pointer->value, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a.pointer->value))
        z = z->right;
      else
        break;
    }
    erase(z);
  }
  inline void Erase(const VALUE_TYPE& a) {
    node* z = root;
    while (true) {
      --z->size;
      if (COMPARER_TYPE()(a, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a))
        z = z->right;
      else
        break;
    }
    if (!--z->count) erase(z);
  }
  inline int Count(const VALUE_TYPE& a) {
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a))
        z = z->right;
      else
        return z->count;
    }
    return 0;
  }
  inline int CountLess(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(z->value, a)) {
        r += z->left->size + z->count;
        z = z->right;
      } else
        z = z->left;
    }
    return r;
  }
  inline int CountLessEqual(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (!COMPARER_TYPE()(a, z->value)) {
        r += z->left->size + z->count;
        z = z->right;
      } else
        z = z->left;
    }
    return r;
  }
  inline int CountGreater(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value)) {
        r += z->right->size + z->count;
        z = z->left;
      } else
        z = z->right;
    }
    return r;
  }
  inline int CountGreaterEqual(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (!COMPARER_TYPE()(z->value, a)) {
        r += z->right->size + z->count;
        z = z->left;
      } else
        z = z->right;
    }
    return r;
  }
  inline Iterator NthElement(int a) {
    node* z = root;
    while (true) {
      if (z->left->size > a)
        z = z->left;
      else if (z->left->size + z->count <= a) {
        a -= z->left->size + z->count;
        z = z->right;
      } else
        return Iterator(z);
    }
  }
  inline Iterator Precursor(const VALUE_TYPE& a) {
    node *z = root, *r = nil;
    while (z != nil) {
      if (COMPARER_TYPE()(z->value, a)) {
        r = z;
        z = z->right;
      } else
        z = z->left;
    }
    return Iterator(r);
  }
  inline Iterator Successor(const VALUE_TYPE& a) {
    node *z = root, *r = nil;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value)) {
        r = z;
        z = z->left;
      } else
        z = z->right;
    }
    return Iterator(r);
  }
  inline int Size() { return root->size; }
  inline int Empty() { return root->size == 0; }
  inline VALUE_TYPE Front() { return *Begin(); }
  inline VALUE_TYPE Back() { return *ReverseBegin(); }
};
}  // namespace DataStructures
namespace NetworkFlow {
template <typename FLOW_TYPE>
class MaxFlow {
 private:
  class edge {
   public:
    int v;
    FLOW_TYPE c;
    inline edge(const int& _v, const FLOW_TYPE& _c) : v(_v), c(_c) {}
  };
  std::vector<edge> edges;
  std::vector<std::vector<int> > start;
  std::vector<int> height, gap, cur, from;
  int n, source, sink;
  FLOW_TYPE limit;
  inline void label() {
    height[sink] = 0;
    std::queue<int> qu;
    qu.push(sink);
    while (!qu.empty()) {
      int u = qu.front();
      qu.pop();
      for (std::vector<int>::iterator i = start[u].begin(); i != start[u].end();
           ++i) {
        edge &e = edges[*i], &ev = edges[(*i) ^ 1];
        if (ev.c != FLOW_TYPE(0) && height[e.v] == n) {
          height[e.v] = height[u] + 1;
          qu.push(e.v);
        }
      }
    }
    for (int i = 0; i < n; ++i) ++gap[height[i]];
  }
  inline FLOW_TYPE augment() {
    FLOW_TYPE f = limit;
    for (int u = sink; u != source; u = edges[from[u] ^ 1].v)
      f = std::min(f, edges[from[u]].c);
    for (int u = sink; u != source; u = edges[from[u] ^ 1].v) {
      edges[from[u]].c -= f;
      edges[from[u] ^ 1].c += f;
    }
    return f;
  }

 public:
  inline MaxFlow(const int& _n, const int& _source, const int& _sink,
                 const FLOW_TYPE& _limit)
      : start(_n),
        height(_n, _n),
        gap(_n + 1),
        n(_n),
        cur(_n),
        from(_n),
        source(_source),
        sink(_sink),
        limit(_limit) {}
  inline void AddEdge(const int& u, const int& v, const FLOW_TYPE& c) {
    start[u].push_back(edges.size());
    edges.push_back(edge(v, c));
    start[v].push_back(edges.size());
    edges.push_back(edge(u, FLOW_TYPE(0)));
  }
  inline FLOW_TYPE Run() {
    label();
    FLOW_TYPE r = FLOW_TYPE(0);
    int u = source;
    while (height[source] != n && limit != FLOW_TYPE(0)) {
      if (u == sink) {
        FLOW_TYPE t = augment();
        limit -= t;
        r += t;
        u = source;
      }
      bool flag = false;
      for (std::vector<int>::iterator i = start[u].begin() + cur[u];
           i != start[u].end(); ++i, ++cur[u]) {
        edge& e = edges[*i];
        if (e.c != FLOW_TYPE(0) && height[u] == height[e.v] + 1) {
          flag = true;
          from[e.v] = *i;
          cur[u] = i - start[u].begin();
          u = e.v;
          break;
        }
      }
      if (!flag) {
        int mh = n - 1;
        for (std::vector<int>::iterator i = start[u].begin();
             i != start[u].end(); ++i) {
          edge& e = edges[*i];
          if (e.c != FLOW_TYPE(0)) mh = std::min(mh, height[e.v]);
        }
        if (!--gap[height[u]]) break;
        ++gap[height[u] = mh + 1];
        cur[u] = 0;
        if (u != source) u = edges[from[u] ^ 1].v;
      }
    }
    return r;
  }
};
template <typename FLOW_TYPE>
class MaxFlow2 {
 private:
  class edge {
   public:
    int v;
    FLOW_TYPE c;
    inline edge(const int& _v, const FLOW_TYPE& _c) : v(_v), c(_c) {}
  };
  std::vector<edge> edges;
  std::vector<std::vector<int> > start;
  std::vector<int> height, cur, gap;
  std::vector<FLOW_TYPE> save;
  int n, source, sink;
  inline void label() {
    height[sink] = 0;
    std::queue<int> qu;
    qu.push(sink);
    while (!qu.empty()) {
      int u = qu.front();
      qu.pop();
      for (std::vector<int>::iterator i = start[u].begin(); i != start[u].end();
           ++i) {
        edge &e = edges[*i], &ev = edges[(*i) ^ 1];
        if (ev.c != FLOW_TYPE(0) && height[e.v] == n) {
          height[e.v] = height[u] + 1;
          qu.push(e.v);
        }
      }
    }
    for (int i = 0; i < n; ++i)
      if (i != source && height[i] > 0 && height[i] < n) ++gap[height[i]];
  }

 public:
  inline MaxFlow2(const int& _n, const int& _source, const int& _sink)
      : start(_n),
        height(_n, _n),
        n(_n),
        cur(_n),
        gap(_n),
        save(_n),
        source(_source),
        sink(_sink) {}
  inline void AddEdge(const int& u, const int& v, const FLOW_TYPE& c) {
    start[u].push_back(edges.size());
    edges.push_back(edge(v, c));
    start[v].push_back(edges.size());
    edges.push_back(edge(u, FLOW_TYPE(0)));
  }
  inline FLOW_TYPE Run() {
    label();
    for (std::vector<int>::iterator i = start[source].begin();
         i != start[source].end(); ++i) {
      edge &e = edges[*i], &ev = edges[(*i) ^ 1];
      save[e.v] += e.c;
      save[source] -= e.c;
      ev.c += e.c;
      e.c = 0;
    }
    std::vector<int> nxt(n), pre(n);
    nxt[source] = sink;
    pre[sink] = source;
    for (int i = 0; i < n; ++i)
      if (i != source && i != sink) {
        nxt[i] = nxt[source];
        pre[nxt[source]] = i;
        nxt[source] = i;
        pre[i] = source;
      }
    for (int u = nxt[source]; u != sink; u = nxt[u]) {
      bool flag = false;
      while (save[u] > FLOW_TYPE(0)) {
        for (std::vector<int>::iterator i = start[u].begin();
             i != start[u].end(); ++i, ++cur[u]) {
          edge &e = edges[*i], &ev = edges[(*i) ^ 1];
          if (e.c != FLOW_TYPE(0) && height[u] == height[e.v] + 1) {
            FLOW_TYPE t = std::min(save[u], e.c);
            save[e.v] += t;
            save[u] -= t;
            ev.c += t;
            e.c -= t;
            if (save[u] == FLOW_TYPE(0)) break;
          }
        }
        if (save[u] != FLOW_TYPE(0)) {
          int mh = 2 * n - 2;
          for (std::vector<int>::iterator i = start[u].begin();
               i != start[u].end(); ++i) {
            edge& e = edges[*i];
            if (e.c != FLOW_TYPE(0)) mh = std::min(mh, height[e.v]);
          }
          int old = height[u];
          if (height[u] > 0 && height[u] < n) --gap[height[u]];
          height[u] = mh + 1;
          if (height[u] > 0 && height[u] < n) ++gap[height[u]];
          if (old > 0 && old < n && !gap[old])
            for (int i = 0; i < n; ++i)
              if (i != source && height[i] > old) {
                if (height[i] < n) --gap[height[i]];
                height[i] = std::max(height[i], n + 1);
                cur[i] = 0;
              }
          cur[u] = 0;
          flag = true;
        }
      }
      if (flag) {
        nxt[pre[u]] = nxt[u];
        pre[nxt[u]] = pre[u];
        pre[nxt[source]] = u;
        nxt[u] = nxt[source];
        nxt[source] = u;
        pre[u] = source;
      }
    }
    return save[sink];
  }
};
}  // namespace NetworkFlow
using namespace std;
using namespace CoreLibrary;
using namespace DataStructures;
using namespace NetworkFlow;
int tmain() {
  Reader reader("1.in");
  Writer writer("1.out");
  int n, m;
  reader >> n >> m;
  MaxFlow2<long long> flow(n, 0, n - 1);
  for (int i = 1; i <= m; ++i) {
    int u, v, c;
    reader >> u >> v >> c;
    flow.AddEdge(u - 1, v - 1, c);
    flow.AddEdge(v - 1, u - 1, c);
  }
  writer << flow.Run() << '\n';
  return 0;
}
template <typename value_type>
inline void read_value(value_type& a) {
  char c;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  a = value_type(0);
  bool flag = c == '-';
  for (; isdigit(c); c = getchar())
    a = a * value_type(10) + value_type(c - '0');
  if (flag) a = -a;
}
template <typename value_type>
inline void print_value(value_type a) {
  bool flag = a < value_type(0);
  if (flag) a = -a;
  std::vector<char> t;
  do {
    t.push_back(a % 10 + '0');
    a /= 10;
  } while (a != value_type(0));
  if (flag) putchar('-');
  for (int i = int(t.size()) - 1; i >= 0; --i) putchar(t[i]);
}
const int MAX_SIDE = 2000010, MAX_NODE = 20010;
class network_flow {
 private:
  int label[MAX_NODE], GAP[MAX_NODE];
  bool visited[MAX_NODE];
  int in_flow[MAX_NODE];
  int vS, vT;
  int tot_node, label_max;
  queue<int> active[MAX_NODE];

 public:
  struct EDGES {
    int pre[MAX_SIDE], val[MAX_SIDE], node[MAX_SIDE], last[MAX_NODE];
    int tot;
    EDGES() { tot = 1; }
    void add_edge(int s, int t, int v) {
      tot++;
      pre[tot] = last[s];
      node[tot] = t;
      val[tot] = v;
      last[s] = tot;
    }
  } edge;
  void set_s(int s) { vS = s; }
  void set_t(int t) { vT = t; }
  void set_tot_node(int n) { tot_node = n; }
  void HLPP() {
    get_length();
    prepare();
    max_flow();
  }
  void add_edge(int s, int t, int v) {
    ++s;
    ++t;
    edge.add_edge(s, t, v);
    edge.add_edge(t, s, 0);
  }
  void max_flow() {
    while (label_max) {
      if (active[label_max].empty()) {
        label_max--;
        continue;
      }
      int now = active[label_max].front(), ext, val;
      int label_min = tot_node + 1;
      int push_flow;
      active[label_max].pop();
      for (int pos(edge.last[now]); pos; pos = edge.pre[pos]) {
        ext = edge.node[pos];
        val = edge.val[pos];
        if (val > 0) {
          if (label[ext] + 1 == label[now]) {
            push_flow = min(val, in_flow[now]);
            edge.val[pos] -= push_flow;
            edge.val[pos ^ 1] += push_flow;
            in_flow[now] -= push_flow;
            in_flow[ext] += push_flow;
            if (push_flow) active[label[ext]].push(ext);
          }
        }
        if (edge.val[pos]) label_min = min(label_min, label[ext]);
        if (!in_flow[now]) break;
      }
      if (in_flow[now] && now != vT && label_min < tot_node) {
        int cache = label[now];
        GAP[label[now]]--;
        label[now] = label_min + 1;
        GAP[label[now]]++;
        if (GAP[cache] == 0) {
          for (int i(1); i <= tot_node; ++i)
            if (label[i] > cache && label[i] < tot_node + 1) {
              GAP[label[i]]--;
              GAP[tot_node + 1]++;
              label[i] = tot_node + 1;
            }
        }
        active[label[now]].push(now);
        if (label[now] > label_max) label_max = label[now];
      }
    }
  }
  void prepare() {
    for (int pos(edge.last[vS]); pos; pos = edge.pre[pos]) {
      int ext = edge.node[pos], val = edge.val[pos];
      if (val > 0) {
        in_flow[ext] += val;
        edge.val[pos] -= val;
        edge.val[pos ^ 1] += val;
        if (label[ext] > label_max) label_max = label[ext];
        active[label[ext]].push(ext);
      }
    }
  }
  void get_length() {
    int queue[MAX_NODE];
    fill(label + 1, label + 1 + tot_node, tot_node + 1);
    memset(visited, 0, sizeof(visited));
    queue[0] = vT;
    label[vT] = 0;
    visited[vT] = 1;
    GAP[0] = 1;
    GAP[tot_node + 1] = tot_node - 1;
    for (int p1(0), p2(0); p1 <= p2; ++p1) {
      int now = queue[p1], ext;
      for (int pos(edge.last[now]); pos; pos = edge.pre[pos]) {
        ext = edge.node[pos];
        if (!visited[ext]) {
          visited[ext] = 1;
          queue[++p2] = ext;
          label[ext] = label[now] + 1;
          GAP[tot_node + 1]--;
          GAP[label[ext]]++;
        }
      }
    }
  }
  int get_ans() { return in_flow[vT]; }
} net;
int n, m, g, sex[10010];
int main() {
  read_value(n);
  read_value(m);
  read_value(g);
  net.set_s(1);
  net.set_t(n + m + 2);
  net.set_tot_node(n + m + 2);
  for (int i = 1; i <= n; ++i) read_value(sex[i]);
  for (int i = 1; i <= n; ++i) {
    int v;
    read_value(v);
    if (!sex[i])
      net.add_edge(0, i, v);
    else
      net.add_edge(i, n + m + 1, v);
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    int tsex, w, k, isf;
    read_value(tsex);
    read_value(w);
    read_value(k);
    ans += w;
    for (int j = 1; j <= k; ++j) {
      int t;
      read_value(t);
      if (!tsex)
        net.add_edge(n + i, t, ~0u >> 1);
      else
        net.add_edge(t, n + i, ~0u >> 1);
    }
    read_value(isf);
    if (!tsex)
      net.add_edge(0, n + i, w + isf * g);
    else
      net.add_edge(n + i, n + m + 1, w + isf * g);
  }
  net.HLPP();
  print_value(ans - net.get_ans());
  putchar('\n');
  return 0;
}

### Prompt

Generate a Cpp solution to 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>
namespace CoreLibrary {
class Reader {
 private:
  std::FILE* file;
  std::vector<char> buffer;
  char *pointer, *end;
  inline void read_file() {
    for (int i = 0;; ++i) {
      buffer.resize(buffer.size() + (1 << i));
      int t =
          std::fread(&buffer[0] + buffer.size() - (1 << i), 1, (1 << i), file);
      if (t != (1 << i)) {
        pointer = &buffer[0];
        end = pointer + buffer.size() - (1 << i) + t;
        break;
      }
    }
  }
  inline void read(char& a) { a = *pointer++; }
  inline void read(char* a) {
    ignore();
    while (pointer != end && !std::isspace(*pointer)) *a++ = *pointer++;
    *a = 0;
  }
  inline void read(int& a) {
    ignore();
    bool f = false;
    if (*pointer == '-') {
      f = true;
      ++pointer;
    }
    a = 0;
    while (pointer != end && std::isdigit(*pointer))
      a = a * 10 + *pointer++ - '0';
    if (f) a = -a;
  }
  inline void read(long long& a) {
    ignore();
    bool f = false;
    if (*pointer == '-') {
      f = true;
      ++pointer;
    }
    a = 0;
    while (pointer != end && std::isdigit(*pointer))
      a = a * 10 + *pointer++ - '0';
    if (f) a = -a;
  }
  inline void ignore() {
    while (pointer != end && std::isspace(*pointer)) ++pointer;
  }

 public:
  inline Reader(std::FILE* _file) : file(_file) { read_file(); }
  inline Reader(std::string _file) : file(std::fopen(_file.c_str(), "r")) {
    read_file();
  }
  inline ~Reader() { fclose(file); }
  template <class VALUE_TYPE>
  inline Reader& operator>>(VALUE_TYPE& a) {
    read(a);
    return *this;
  }
};
class Writer {
 private:
  std::FILE* file;
  std::vector<char> buffer;
  inline void write(char a) { buffer.push_back(a); }
  inline void write(const char* a) {
    while (*a) buffer.push_back(*a++);
  }
  inline void write(int a) {
    if (a < 0) {
      buffer.push_back('-');
      a = -a;
    }
    static char t[10];
    char* p = t;
    do {
      int b = a / 10;
      *p++ = a - b * 10 + '0';
      a = b;
    } while (a);
    while (p > t) buffer.push_back(*--p);
  }
  inline void write(long long a) {
    if (a < 0) {
      buffer.push_back('-');
      a = -a;
    }
    static char t[19];
    char* p = t;
    do {
      long long b = a / 10;
      *p++ = a - b * 10 + '0';
      a = b;
    } while (a);
    while (p > t) buffer.push_back(*--p);
  }

 public:
  inline Writer(std::FILE* _file) : file(_file) {}
  inline Writer(std::string _file) : file(std::fopen(_file.c_str(), "w")) {}
  inline ~Writer() {
    std::fwrite(&buffer[0], 1, buffer.size(), file);
    fclose(file);
  }
  template <class VALUE_TYPE>
  inline Writer& operator<<(VALUE_TYPE a) {
    write(a);
    return *this;
  }
};
template <class VALUE_TYPE>
inline bool MakeMax(VALUE_TYPE& a, const VALUE_TYPE& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class VALUE_TYPE>
inline bool MakeMin(VALUE_TYPE& a, const VALUE_TYPE& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class VALUE_TYPE>
inline VALUE_TYPE Abs(const VALUE_TYPE& a) {
  return a < VALUE_TYPE(0) ? -a : a;
}
}  // namespace CoreLibrary
namespace DataStructures {
template <class VALUE_TYPE, class COMPARER_TYPE>
class Set {
 private:
  struct node {
    inline node(const VALUE_TYPE& _value, node* _left, node* _right,
                node* _parent, const bool& _black, const int& _size,
                const int& _count)
        : value(_value),
          left(_left),
          right(_right),
          parent(_parent),
          black(_black),
          size(_size),
          count(_count) {}
    VALUE_TYPE value;
    node *left, *right, *parent;
    bool black;
    int size, count;
  } * root, *nil;
  inline void clear(node* x) {
    if (x != nil) {
      clear(x->left);
      clear(x->right);
      delete x;
    }
  }
  inline void left_rotate(node* x) {
    node* y = x->right;
    x->right = y->left;
    if (y->left != nil) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == nil)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else
      x->parent->right = y;
    y->left = x;
    x->parent = y;
    y->size = x->size;
    x->size = x->left->size + x->right->size + x->count;
  }
  inline void right_rotate(node* x) {
    node* y = x->left;
    x->left = y->right;
    if (y->right != nil) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == nil)
      root = y;
    else if (x == x->parent->left)
      x->parent->left = y;
    else
      x->parent->right = y;
    y->right = x;
    x->parent = y;
    y->size = x->size;
    x->size = x->left->size + x->right->size + x->count;
  }
  inline void insert_fixup(node* z) {
    while (!z->parent->black) {
      if (z->parent == z->parent->parent->left) {
        node* y = z->parent->parent->right;
        if (!y->black) {
          z->parent->black = true;
          y->black = true;
          (z = z->parent->parent)->black = false;
        } else {
          if (z == z->parent->right) left_rotate(z = z->parent);
          z->parent->black = true;
          z->parent->parent->black = false;
          right_rotate(z->parent->parent);
        }
      } else {
        node* y = z->parent->parent->left;
        if (!y->black) {
          z->parent->black = true;
          y->black = true;
          (z = z->parent->parent)->black = false;
        } else {
          if (z == z->parent->left) right_rotate(z = z->parent);
          z->parent->black = true;
          z->parent->parent->black = false;
          left_rotate(z->parent->parent);
        }
      }
    }
    root->black = true;
  }
  inline void erase(node* z) {
    node* y;
    if (z->left == nil || z->right == nil)
      y = z;
    else {
      y = z->right;
      while (y->left != nil) y = y->left;
      z->value = y->value;
      z->count = y->count;
      int t = y->count;
      y->count = 0;
      y = z->right;
      while (y->left != nil) {
        y->size -= t;
        y = y->left;
      }
    }
    node* x = y->left == nil ? y->right : y->left;
    x->parent = y->parent;
    if (y->parent == nil)
      root = x;
    else if (y == y->parent->left)
      y->parent->left = x;
    else
      y->parent->right = x;
    if (y->black) erase_fixup(x);
    delete y;
  }
  inline void erase_fixup(node* x) {
    while (x != root && x->black) {
      if (x == x->parent->left) {
        node* w = x->parent->right;
        if (!w->black) {
          w->black = true;
          x->parent->black = false;
          left_rotate(x->parent);
          w = x->parent->right;
        }
        if (w->left->black && w->right->black) {
          w->black = false;
          x = x->parent;
        } else {
          if (w->right->black) {
            w->left->black = true;
            w->black = false;
            right_rotate(w);
            w = x->parent->right;
          }
          w->black = x->parent->black;
          x->parent->black = true;
          w->right->black = true;
          left_rotate(x->parent);
          x = root;
        }
      } else {
        node* w = x->parent->left;
        if (!w->black) {
          w->black = true;
          x->parent->black = false;
          right_rotate(x->parent);
          w = x->parent->left;
        }
        if (w->left->black && w->right->black) {
          w->black = false;
          x = x->parent;
        } else {
          if (w->left->black) {
            w->right->black = true;
            w->black = false;
            left_rotate(w);
            w = x->parent->left;
          }
          w->black = x->parent->black;
          x->parent->black = true;
          w->left->black = true;
          right_rotate(x->parent);
          x = root;
        }
      }
    }
    x->black = true;
  }
  inline node* clone(node* x, node* y) {
    if (!x->count) return nil;
    node* z = new node(*x);
    z->left = clone(x->left, z);
    z->right = clone(x->right, z);
    z->parent = y;
    return z;
  }

 public:
  class Iterator {
   private:
    node* pointer;
    friend class Set;
    inline node* precursor(node* x) {
      if (x->left->count) {
        x = x->left;
        while (x->right->count) x = x->right;
        return x;
      } else {
        node* y = x->parent;
        while (y->count && x == y->left) {
          x = y;
          y = y->parent;
        }
        return y;
      }
    }
    inline node* successor(node* x) {
      if (x->right->count) {
        x = x->right;
        while (x->left->count) x = x->left;
        return x;
      } else {
        node* y = x->parent;
        while (y->count && x == y->right) {
          x = y;
          y = y->parent;
        }
        return y;
      }
    }

   public:
    inline Iterator(node* _pointer) : pointer(_pointer) {}
    inline ~Iterator() {}
    inline bool operator==(const Iterator& a) { return pointer == a.pointer; }
    inline bool operator!=(const Iterator& a) { return pointer != a.pointer; }
    inline VALUE_TYPE operator*() { return pointer->value; }
    inline VALUE_TYPE* operator->() { return &pointer->value; }
    inline Iterator& operator++() {
      pointer = successor(pointer);
      return *this;
    }
    inline Iterator operator++(int) {
      Iterator t = *this;
      pointer = successor(pointer);
      return t;
    }
    inline Iterator& operator--() {
      pointer = precursor(pointer);
      return *this;
    }
    inline Iterator operator--(int) {
      Iterator t = *this;
      pointer = precursor(pointer);
      return t;
    }
  };
  inline Set() { root = nil = new node(VALUE_TYPE(), 0, 0, 0, true, 0, 0); }
  inline Set(const Set& a) {
    nil = new node(*a.nil);
    root = clone(a.root, nil);
  }
  inline ~Set() {
    clear(root);
    delete nil;
  }
  inline Set& operator=(const Set& a) {
    clear(root);
    root = clone(a.root, nil);
    return *this;
  }
  Iterator Begin() {
    node* z = root;
    while (z != nil && z->left != nil) z = z->left;
    return Iterator(z);
  }
  Iterator ReverseBegin() {
    node* z = root;
    while (z != nil && z->right != nil) z = z->right;
    return Iterator(z);
  }
  Iterator End() { return Iterator(nil); }
  Iterator ReverseEnd() { return Iterator(nil); }
  inline void Clear() {
    clear(root);
    root = nil;
  }
  inline void Insert(const VALUE_TYPE& a) {
    node *y = nil, *x = root;
    while (x != nil) {
      y = x;
      ++x->size;
      if (COMPARER_TYPE()(a, x->value))
        x = x->left;
      else if (COMPARER_TYPE()(x->value, a))
        x = x->right;
      else {
        ++x->count;
        return;
      }
    }
    node* z = new node(a, nil, nil, y, false, 1, 1);
    if (y == nil)
      root = z;
    else if (COMPARER_TYPE()(z->value, y->value))
      y->left = z;
    else
      y->right = z;
    insert_fixup(z);
  }
  inline void Erase(const Iterator& a) {
    node* z = root;
    while (true) {
      z->size -= a.pointer->count;
      if (COMPARER_TYPE()(a.pointer->value, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a.pointer->value))
        z = z->right;
      else
        break;
    }
    erase(z);
  }
  inline void Erase(const VALUE_TYPE& a) {
    node* z = root;
    while (true) {
      --z->size;
      if (COMPARER_TYPE()(a, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a))
        z = z->right;
      else
        break;
    }
    if (!--z->count) erase(z);
  }
  inline int Count(const VALUE_TYPE& a) {
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value))
        z = z->left;
      else if (COMPARER_TYPE()(z->value, a))
        z = z->right;
      else
        return z->count;
    }
    return 0;
  }
  inline int CountLess(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(z->value, a)) {
        r += z->left->size + z->count;
        z = z->right;
      } else
        z = z->left;
    }
    return r;
  }
  inline int CountLessEqual(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (!COMPARER_TYPE()(a, z->value)) {
        r += z->left->size + z->count;
        z = z->right;
      } else
        z = z->left;
    }
    return r;
  }
  inline int CountGreater(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value)) {
        r += z->right->size + z->count;
        z = z->left;
      } else
        z = z->right;
    }
    return r;
  }
  inline int CountGreaterEqual(const VALUE_TYPE& a) {
    int r = 0;
    node* z = root;
    while (z != nil) {
      if (!COMPARER_TYPE()(z->value, a)) {
        r += z->right->size + z->count;
        z = z->left;
      } else
        z = z->right;
    }
    return r;
  }
  inline Iterator NthElement(int a) {
    node* z = root;
    while (true) {
      if (z->left->size > a)
        z = z->left;
      else if (z->left->size + z->count <= a) {
        a -= z->left->size + z->count;
        z = z->right;
      } else
        return Iterator(z);
    }
  }
  inline Iterator Precursor(const VALUE_TYPE& a) {
    node *z = root, *r = nil;
    while (z != nil) {
      if (COMPARER_TYPE()(z->value, a)) {
        r = z;
        z = z->right;
      } else
        z = z->left;
    }
    return Iterator(r);
  }
  inline Iterator Successor(const VALUE_TYPE& a) {
    node *z = root, *r = nil;
    while (z != nil) {
      if (COMPARER_TYPE()(a, z->value)) {
        r = z;
        z = z->left;
      } else
        z = z->right;
    }
    return Iterator(r);
  }
  inline int Size() { return root->size; }
  inline int Empty() { return root->size == 0; }
  inline VALUE_TYPE Front() { return *Begin(); }
  inline VALUE_TYPE Back() { return *ReverseBegin(); }
};
}  // namespace DataStructures
namespace NetworkFlow {
template <typename FLOW_TYPE>
class MaxFlow {
 private:
  class edge {
   public:
    int v;
    FLOW_TYPE c;
    inline edge(const int& _v, const FLOW_TYPE& _c) : v(_v), c(_c) {}
  };
  std::vector<edge> edges;
  std::vector<std::vector<int> > start;
  std::vector<int> height, gap, cur, from;
  int n, source, sink;
  FLOW_TYPE limit;
  inline void label() {
    height[sink] = 0;
    std::queue<int> qu;
    qu.push(sink);
    while (!qu.empty()) {
      int u = qu.front();
      qu.pop();
      for (std::vector<int>::iterator i = start[u].begin(); i != start[u].end();
           ++i) {
        edge &e = edges[*i], &ev = edges[(*i) ^ 1];
        if (ev.c != FLOW_TYPE(0) && height[e.v] == n) {
          height[e.v] = height[u] + 1;
          qu.push(e.v);
        }
      }
    }
    for (int i = 0; i < n; ++i) ++gap[height[i]];
  }
  inline FLOW_TYPE augment() {
    FLOW_TYPE f = limit;
    for (int u = sink; u != source; u = edges[from[u] ^ 1].v)
      f = std::min(f, edges[from[u]].c);
    for (int u = sink; u != source; u = edges[from[u] ^ 1].v) {
      edges[from[u]].c -= f;
      edges[from[u] ^ 1].c += f;
    }
    return f;
  }

 public:
  inline MaxFlow(const int& _n, const int& _source, const int& _sink,
                 const FLOW_TYPE& _limit)
      : start(_n),
        height(_n, _n),
        gap(_n + 1),
        n(_n),
        cur(_n),
        from(_n),
        source(_source),
        sink(_sink),
        limit(_limit) {}
  inline void AddEdge(const int& u, const int& v, const FLOW_TYPE& c) {
    start[u].push_back(edges.size());
    edges.push_back(edge(v, c));
    start[v].push_back(edges.size());
    edges.push_back(edge(u, FLOW_TYPE(0)));
  }
  inline FLOW_TYPE Run() {
    label();
    FLOW_TYPE r = FLOW_TYPE(0);
    int u = source;
    while (height[source] != n && limit != FLOW_TYPE(0)) {
      if (u == sink) {
        FLOW_TYPE t = augment();
        limit -= t;
        r += t;
        u = source;
      }
      bool flag = false;
      for (std::vector<int>::iterator i = start[u].begin() + cur[u];
           i != start[u].end(); ++i, ++cur[u]) {
        edge& e = edges[*i];
        if (e.c != FLOW_TYPE(0) && height[u] == height[e.v] + 1) {
          flag = true;
          from[e.v] = *i;
          cur[u] = i - start[u].begin();
          u = e.v;
          break;
        }
      }
      if (!flag) {
        int mh = n - 1;
        for (std::vector<int>::iterator i = start[u].begin();
             i != start[u].end(); ++i) {
          edge& e = edges[*i];
          if (e.c != FLOW_TYPE(0)) mh = std::min(mh, height[e.v]);
        }
        if (!--gap[height[u]]) break;
        ++gap[height[u] = mh + 1];
        cur[u] = 0;
        if (u != source) u = edges[from[u] ^ 1].v;
      }
    }
    return r;
  }
};
template <typename FLOW_TYPE>
class MaxFlow2 {
 private:
  class edge {
   public:
    int v;
    FLOW_TYPE c;
    inline edge(const int& _v, const FLOW_TYPE& _c) : v(_v), c(_c) {}
  };
  std::vector<edge> edges;
  std::vector<std::vector<int> > start;
  std::vector<int> height, cur, gap;
  std::vector<FLOW_TYPE> save;
  int n, source, sink;
  inline void label() {
    height[sink] = 0;
    std::queue<int> qu;
    qu.push(sink);
    while (!qu.empty()) {
      int u = qu.front();
      qu.pop();
      for (std::vector<int>::iterator i = start[u].begin(); i != start[u].end();
           ++i) {
        edge &e = edges[*i], &ev = edges[(*i) ^ 1];
        if (ev.c != FLOW_TYPE(0) && height[e.v] == n) {
          height[e.v] = height[u] + 1;
          qu.push(e.v);
        }
      }
    }
    for (int i = 0; i < n; ++i)
      if (i != source && height[i] > 0 && height[i] < n) ++gap[height[i]];
  }

 public:
  inline MaxFlow2(const int& _n, const int& _source, const int& _sink)
      : start(_n),
        height(_n, _n),
        n(_n),
        cur(_n),
        gap(_n),
        save(_n),
        source(_source),
        sink(_sink) {}
  inline void AddEdge(const int& u, const int& v, const FLOW_TYPE& c) {
    start[u].push_back(edges.size());
    edges.push_back(edge(v, c));
    start[v].push_back(edges.size());
    edges.push_back(edge(u, FLOW_TYPE(0)));
  }
  inline FLOW_TYPE Run() {
    label();
    for (std::vector<int>::iterator i = start[source].begin();
         i != start[source].end(); ++i) {
      edge &e = edges[*i], &ev = edges[(*i) ^ 1];
      save[e.v] += e.c;
      save[source] -= e.c;
      ev.c += e.c;
      e.c = 0;
    }
    std::vector<int> nxt(n), pre(n);
    nxt[source] = sink;
    pre[sink] = source;
    for (int i = 0; i < n; ++i)
      if (i != source && i != sink) {
        nxt[i] = nxt[source];
        pre[nxt[source]] = i;
        nxt[source] = i;
        pre[i] = source;
      }
    for (int u = nxt[source]; u != sink; u = nxt[u]) {
      bool flag = false;
      while (save[u] > FLOW_TYPE(0)) {
        for (std::vector<int>::iterator i = start[u].begin();
             i != start[u].end(); ++i, ++cur[u]) {
          edge &e = edges[*i], &ev = edges[(*i) ^ 1];
          if (e.c != FLOW_TYPE(0) && height[u] == height[e.v] + 1) {
            FLOW_TYPE t = std::min(save[u], e.c);
            save[e.v] += t;
            save[u] -= t;
            ev.c += t;
            e.c -= t;
            if (save[u] == FLOW_TYPE(0)) break;
          }
        }
        if (save[u] != FLOW_TYPE(0)) {
          int mh = 2 * n - 2;
          for (std::vector<int>::iterator i = start[u].begin();
               i != start[u].end(); ++i) {
            edge& e = edges[*i];
            if (e.c != FLOW_TYPE(0)) mh = std::min(mh, height[e.v]);
          }
          int old = height[u];
          if (height[u] > 0 && height[u] < n) --gap[height[u]];
          height[u] = mh + 1;
          if (height[u] > 0 && height[u] < n) ++gap[height[u]];
          if (old > 0 && old < n && !gap[old])
            for (int i = 0; i < n; ++i)
              if (i != source && height[i] > old) {
                if (height[i] < n) --gap[height[i]];
                height[i] = std::max(height[i], n + 1);
                cur[i] = 0;
              }
          cur[u] = 0;
          flag = true;
        }
      }
      if (flag) {
        nxt[pre[u]] = nxt[u];
        pre[nxt[u]] = pre[u];
        pre[nxt[source]] = u;
        nxt[u] = nxt[source];
        nxt[source] = u;
        pre[u] = source;
      }
    }
    return save[sink];
  }
};
}  // namespace NetworkFlow
using namespace std;
using namespace CoreLibrary;
using namespace DataStructures;
using namespace NetworkFlow;
int tmain() {
  Reader reader("1.in");
  Writer writer("1.out");
  int n, m;
  reader >> n >> m;
  MaxFlow2<long long> flow(n, 0, n - 1);
  for (int i = 1; i <= m; ++i) {
    int u, v, c;
    reader >> u >> v >> c;
    flow.AddEdge(u - 1, v - 1, c);
    flow.AddEdge(v - 1, u - 1, c);
  }
  writer << flow.Run() << '\n';
  return 0;
}
template <typename value_type>
inline void read_value(value_type& a) {
  char c;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  a = value_type(0);
  bool flag = c == '-';
  for (; isdigit(c); c = getchar())
    a = a * value_type(10) + value_type(c - '0');
  if (flag) a = -a;
}
template <typename value_type>
inline void print_value(value_type a) {
  bool flag = a < value_type(0);
  if (flag) a = -a;
  std::vector<char> t;
  do {
    t.push_back(a % 10 + '0');
    a /= 10;
  } while (a != value_type(0));
  if (flag) putchar('-');
  for (int i = int(t.size()) - 1; i >= 0; --i) putchar(t[i]);
}
const int MAX_SIDE = 2000010, MAX_NODE = 20010;
class network_flow {
 private:
  int label[MAX_NODE], GAP[MAX_NODE];
  bool visited[MAX_NODE];
  int in_flow[MAX_NODE];
  int vS, vT;
  int tot_node, label_max;
  queue<int> active[MAX_NODE];

 public:
  struct EDGES {
    int pre[MAX_SIDE], val[MAX_SIDE], node[MAX_SIDE], last[MAX_NODE];
    int tot;
    EDGES() { tot = 1; }
    void add_edge(int s, int t, int v) {
      tot++;
      pre[tot] = last[s];
      node[tot] = t;
      val[tot] = v;
      last[s] = tot;
    }
  } edge;
  void set_s(int s) { vS = s; }
  void set_t(int t) { vT = t; }
  void set_tot_node(int n) { tot_node = n; }
  void HLPP() {
    get_length();
    prepare();
    max_flow();
  }
  void add_edge(int s, int t, int v) {
    ++s;
    ++t;
    edge.add_edge(s, t, v);
    edge.add_edge(t, s, 0);
  }
  void max_flow() {
    while (label_max) {
      if (active[label_max].empty()) {
        label_max--;
        continue;
      }
      int now = active[label_max].front(), ext, val;
      int label_min = tot_node + 1;
      int push_flow;
      active[label_max].pop();
      for (int pos(edge.last[now]); pos; pos = edge.pre[pos]) {
        ext = edge.node[pos];
        val = edge.val[pos];
        if (val > 0) {
          if (label[ext] + 1 == label[now]) {
            push_flow = min(val, in_flow[now]);
            edge.val[pos] -= push_flow;
            edge.val[pos ^ 1] += push_flow;
            in_flow[now] -= push_flow;
            in_flow[ext] += push_flow;
            if (push_flow) active[label[ext]].push(ext);
          }
        }
        if (edge.val[pos]) label_min = min(label_min, label[ext]);
        if (!in_flow[now]) break;
      }
      if (in_flow[now] && now != vT && label_min < tot_node) {
        int cache = label[now];
        GAP[label[now]]--;
        label[now] = label_min + 1;
        GAP[label[now]]++;
        if (GAP[cache] == 0) {
          for (int i(1); i <= tot_node; ++i)
            if (label[i] > cache && label[i] < tot_node + 1) {
              GAP[label[i]]--;
              GAP[tot_node + 1]++;
              label[i] = tot_node + 1;
            }
        }
        active[label[now]].push(now);
        if (label[now] > label_max) label_max = label[now];
      }
    }
  }
  void prepare() {
    for (int pos(edge.last[vS]); pos; pos = edge.pre[pos]) {
      int ext = edge.node[pos], val = edge.val[pos];
      if (val > 0) {
        in_flow[ext] += val;
        edge.val[pos] -= val;
        edge.val[pos ^ 1] += val;
        if (label[ext] > label_max) label_max = label[ext];
        active[label[ext]].push(ext);
      }
    }
  }
  void get_length() {
    int queue[MAX_NODE];
    fill(label + 1, label + 1 + tot_node, tot_node + 1);
    memset(visited, 0, sizeof(visited));
    queue[0] = vT;
    label[vT] = 0;
    visited[vT] = 1;
    GAP[0] = 1;
    GAP[tot_node + 1] = tot_node - 1;
    for (int p1(0), p2(0); p1 <= p2; ++p1) {
      int now = queue[p1], ext;
      for (int pos(edge.last[now]); pos; pos = edge.pre[pos]) {
        ext = edge.node[pos];
        if (!visited[ext]) {
          visited[ext] = 1;
          queue[++p2] = ext;
          label[ext] = label[now] + 1;
          GAP[tot_node + 1]--;
          GAP[label[ext]]++;
        }
      }
    }
  }
  int get_ans() { return in_flow[vT]; }
} net;
int n, m, g, sex[10010];
int main() {
  read_value(n);
  read_value(m);
  read_value(g);
  net.set_s(1);
  net.set_t(n + m + 2);
  net.set_tot_node(n + m + 2);
  for (int i = 1; i <= n; ++i) read_value(sex[i]);
  for (int i = 1; i <= n; ++i) {
    int v;
    read_value(v);
    if (!sex[i])
      net.add_edge(0, i, v);
    else
      net.add_edge(i, n + m + 1, v);
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    int tsex, w, k, isf;
    read_value(tsex);
    read_value(w);
    read_value(k);
    ans += w;
    for (int j = 1; j <= k; ++j) {
      int t;
      read_value(t);
      if (!tsex)
        net.add_edge(n + i, t, ~0u >> 1);
      else
        net.add_edge(t, n + i, ~0u >> 1);
    }
    read_value(isf);
    if (!tsex)
      net.add_edge(0, n + i, w + isf * g);
    else
      net.add_edge(n + i, n + m + 1, w + isf * g);
  }
  net.HLPP();
  print_value(ans - net.get_ans());
  putchar('\n');
  return 0;
}

```