struct Edge {
     int a, b, cap, flow;
};

struct MaxFlow {
     int n, s, t;
     vector<int> d, ptr, q;
     vector< Edge > e;
     vector< vector<int> > g;

     MaxFlow(int _n) : n(_n), d(_n), ptr(_n), q(_n), g(_n) {
          e.clear();
          for (int i = 0; i < n; i++) {
               g[i].clear();
               ptr[i] = 0;
          }
     }

     void addEdge(int a, int b, int cap) {
          Edge e1 = { a, b, cap, 0 };
          Edge e2 = { b, a, 0, 0 };
          g[a].push_back( (int) e.size() );
          e.push_back(e1);
          g[b].push_back( (int) e.size() );
          e.push_back(e2);
     }
     int getMaxFlow(int _s, int _t) {
          s = _s; t = _t;
          int flow = 0;
          for (;;) {
               if (!bfs()) break;
               std::fill(ptr.begin(), ptr.end(), 0);
               while (int pushed = dfs(s, inf))
                    flow += pushed;
          }
          return flow;
     }

private:
     bool bfs() {
          int qh = 0, qt = 0;
          q[qt++] = s;
          std::fill(d.begin(), d.end(), -1);
          d[s] = 0;

          while (qh < qt && d[t] == -1) {
               int v = q[qh++];
               for (int i = 0; i < (int) g[v].size(); i++) {
                    int id = g[v][i], to = e[id].b;
                    if (d[to] == -1 && e[id].flow < e[id].cap) {
                         q[qt++] = to;
                         d[to] = d[v] + 1;
                    }
               }
          }
          return d[t] != -1;
     }

     int dfs (int v, int flow) {
          if (!flow) return 0;
          if (v == t) return flow;
          for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
               int id = g[v][ptr[v]],
                    to = e[id].b;
               if (d[to] != d[v] + 1) continue;
               int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
               if (pushed) {
                    e[id].flow += pushed;
                    e[id^1].flow -= pushed;
                    return pushed;
               }
          }
          return 0;
     }
};

struct FlowEdge {
     int v, u;
     long long cap, flow = 0;
     FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
 
struct Dinic {
     const long long flow_inf = 1e18;
     vector<FlowEdge> edges;
     vector<vector<int>> adj;
     int n, m = 0;
     int s, t;
     vector<int> level, ptr;
     queue<int> q;
 
     Dinic(int n, int s, int t) : n(n), s(s), t(t) {
          adj.resize(n);
          level.resize(n);
          ptr.resize(n);
     }
 
     void addEdge(int v, int u, long long cap) {
          edges.emplace_back(v, u, cap);
          edges.emplace_back(u, v, 0);
          adj[v].push_back(m);
          adj[u].push_back(m + 1);
          m += 2;
     }
 
     bool bfs() {
          while (!q.empty()) {
               int v = q.front();
               q.pop();
               for (int id : adj[v]) {
                    if (edges[id].cap == edges[id].flow)
                         continue;
                    if (level[edges[id].u] != -1)
                         continue;
                    level[edges[id].u] = level[v] + 1;
                    q.push(edges[id].u);
               }
          }
          return level[t] != -1;
     }
 
     long long dfs(int v, long long pushed) {
          if (pushed == 0)
               return 0;
          if (v == t)
               return pushed;
          for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
               int id = adj[v][cid];
               int u = edges[id].u;
               if (level[v] + 1 != level[u])
                    continue;
               long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
               if (tr == 0)
                    continue;
               edges[id].flow += tr;
               edges[id ^ 1].flow -= tr;
               return tr;
          }
          return 0;
     }
 
     long long getMaxFlow() {
          long long f = 0;
          while (true) {
               fill(level.begin(), level.end(), -1);
               level[s] = 0;
               q.push(s);
               if (!bfs())
                    break;
               fill(ptr.begin(), ptr.end(), 0);
               while (long long pushed = dfs(s, flow_inf)) {
                    f += pushed;
               }
          }
          return f;
     }
};