const int NIL = 0;
const int INF = 1e9;
class BipartiteGraph {
    int m, n; // Number of vertices in left and right partitions
    std::vector<std::list<int>> adj; // Adjacency list
    std::vector<int> pairU, pairV, dist; // Matching arrays and distance array

public:
    BipartiteGraph(int m, int n) : m(m), n(n) {
        adj.resize(m + 1);
        pairU.resize(m + 1);
        pairV.resize(n + 1);
        dist.resize(m + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool bfs() {
        std::queue<int> q;
        for (int u = 1; u <= m; ++u) {
            if (pairU[u] == NIL) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        dist[NIL] = INF; // Special case for NIL

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (dist[u] < dist[NIL]) {
                for (int v : adj[u]) {
                    if (dist[pairV[v]] == INF) {
                        dist[pairV[v]] = dist[u] + 1;
                        q.push(pairV[v]);
                    }
                }
            }
        }
        return (dist[NIL] != INF);
    }

    bool dfs(int u) {
        if (u == NIL) return true;

        for (int v : adj[u]) {
            if (dist[pairV[v]] == dist[u] + 1) {
                if (dfs(pairV[v])) {
                    pairV[v] = u;
                    pairU[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF; // Mark as visited in this phase
        return false;
    }

    int hopcroftKarp() {
        int result = 0;
        while (bfs()) {
            for (int u = 1; u <= m; ++u) {
                if (pairU[u] == NIL && dfs(u)) {
                    result++;
                }
            }
        }
        return result;
    }
};

class MaxFlowMinCost {
    static const int INF = (int)1e9 + 7;
    static const long long LL_INF = (long long)1e18 + 7LL;

    struct Edge {
        int from, to, flow, capa;
        long long cost;

        Edge(int _from = 0, int _to = 0, int _capa = 0, long long _cost = 0) {
            from = _from; to = _to; flow = 0; capa = _capa; cost = _cost;
        }

        int residual(void) const {
            return capa - flow;
        }
    };

    int numNode;
    vector<vector<int>> adj;
    vector<Edge> edges;
    vector<long long> dist;
    vector<int> trc;
    vector<bool> inQueue;

public:
    MaxFlowMinCost(int _numNode = 0) {
        numNode = _numNode;
        adj.assign(numNode + 7, vector<int>());
        dist.assign(numNode + 7, 0);
        trc.assign(numNode + 7, -1);
        inQueue.assign(numNode + 7, false);
    }

    int addEdge(int from, int to, int capa, long long cost) {
        adj[from].push_back(edges.size());
        // cout << edges.size(), el;
        edges.push_back(Edge(from, to, capa, cost));
        adj[to].push_back(edges.size());
        edges.push_back(Edge(to, from, 0, -cost));
        return edges.size() - 2;
    }

private:
    bool fordBellman(int s, int t) {
        fo(i, 1, numNode) {
            dist[i] = LL_INF;
            trc[i] = -1;
            inQueue[i] = false;
        }

        queue<int> q;
        dist[s] = 0; q.push(s); inQueue[s] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop(); inQueue[u] = false;
            for (int id : adj[u]) if (edges[id].residual() > 0) {
                int v = edges[id].to;
                if (dist[v] > dist[u] + edges[id].cost) {
                    dist[v] = dist[u] + edges[id].cost;
                    trc[v] = id;
                    if (!inQueue[v]) {
                         q.push(v); inQueue[v] = true;
                    }
                }
            }
        }

        return dist[t] < LL_INF;
    }

public:
    pair<int, long long> getFlow(int src, int snk) {
        int totFlow = 0;
        long long totCost = 0;

        while (fordBellman(src, snk)) {
            int delta = INF;
            for (int u = snk; u != src; u = edges[trc[u]].from) delta = min(delta, edges[trc[u]].residual());
            for (int u = snk; u != src; u = edges[trc[u]].from) {
                edges[trc[u]].flow += delta;
                edges[trc[u] ^ 1].flow -= delta;
            }
            totFlow += delta;
            totCost += delta * dist[snk];
        }

        return make_pair(totFlow, totCost);
    }

    int traceFlow(int id) const {
        return edges[id].flow;
    }

    void tracePath() {
        fo(i, 0, (int)edges.size() - 1) {
            auto[from, to, flow, capa, cost] = edges[i];
            if (i % 2 == 0 && flow > 0 && from <= numNode) {
                cout << from << ' ' << to << ' ' << flow, el;
            }
        }
        return;
    }
};

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;
     }
};