#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 4e18; // large number for costs / flows

// =====================================================================
// This file contains a collection of Minimum Cost Maximum Flow (MCMF)
// and related Network Flow algorithms. Each function is ready to be used
// as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// =====================================================================

// =====================================================================
// 1) STANDARD MIN-COST MAX-FLOW (MCMF) WITH SPFA
//    Safest and simplest. Handles negative edge costs.
//    Use when graph is small or costs are negative.
// =====================================================================

struct MCMF_SPFA {
    struct Edge {
        int to, rev;   // destination, index of reverse edge
        int cap;       // remaining capacity
        ll cost;       // cost per unit of flow
    };

    int n;
    vector<vector<Edge>> adj;

    MCMF_SPFA(int n) : n(n), adj(n) {}

    // Adds a directed edge u->v with given capacity and cost.
    // Also adds the reverse edge (cap 0, cost -cost).
    void addEdge(int u, int v, int cap, ll cost) {
        Edge a{v, (int)adj[v].size(), cap, cost};
        Edge b{u, (int)adj[u].size(), 0, -cost};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }

    // Sends flow from s to t while minimizing total cost.
    // If maxf == 0, sends as much as possible.
    // Returns pair {flow, cost}.
    // Complexity: O(flow * E * V) worst-case, but usually O(flow * E).
    // Precondition: no negative cost cycles reachable from s.
    pair<int, ll> minCostMaxFlow(int s, int t, int maxf = 0) {
        int flow = 0;
        ll cost = 0;

        while (true) {
            vector<ll> dist(n, INF);
            vector<int> pv(n, -1), pe(n, -1);
            vector<bool> inq(n, false);
            queue<int> q;

            dist[s] = 0;
            q.push(s);
            inq[s] = true;

            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                for (int i = 0; i < (int)adj[u].size(); i++) {
                    Edge &e = adj[u][i];
                    if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u;
                        pe[e.to] = i;
                        if (!inq[e.to]) {
                            q.push(e.to);
                            inq[e.to] = true;
                        }
                    }
                }
            }

            if (dist[t] == INF) break;

            int add = (maxf == 0) ? INT_MAX : maxf;
            for (int v = t; v != s; v = pv[v]) {
                add = min(add, adj[pv[v]][pe[v]].cap);
            }
            if (maxf != 0 && flow + add > maxf) add = maxf - flow;

            for (int v = t; v != s; v = pv[v]) {
                Edge &e = adj[pv[v]][pe[v]];
                e.cap -= add;
                adj[v][e.rev].cap += add;
                cost += (ll)add * e.cost;
            }
            flow += add;

            if (maxf != 0 && flow == maxf) break;
        }
        return {flow, cost};
    }
};

// =====================================================================
// 2) MIN-COST MAX-FLOW WITH DIJKSTRA + POTENTIALS (FAST)
//    Use this for large graphs. Handles negative costs via initial SPFA.
//    Complexity: O(flow * E log V).
// =====================================================================

struct MCMF_Dijkstra {
    struct Edge {
        int to, rev, cap;
        ll cost;
    };

    int n;
    vector<vector<Edge>> adj;
    vector<ll> pot; // Johnson potentials

    MCMF_Dijkstra(int n) : n(n), adj(n), pot(n, 0) {}

    void addEdge(int u, int v, int cap, ll cost) {
        Edge a{v, (int)adj[v].size(), cap, cost};
        Edge b{u, (int)adj[u].size(), 0, -cost};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }

    // Sends flow from s to t with minimum cost.
    // If maxf == 0, sends as much as possible.
    // Returns {flow, cost}.
    // Precondition: no negative cost cycles.
    pair<int, ll> minCostMaxFlow(int s, int t, int maxf = 0) {
        const ll INFLL = INF;
        int flow = 0;
        ll cost = 0;

        // Initial potentials via SPFA (handles negative edges safely)
        vector<ll> dist(n, INFLL);
        vector<bool> inq(n, false);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        inq[s] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (auto &e : adj[u]) {
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    if (!inq[e.to]) {
                        q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (dist[i] < INFLL) pot[i] = dist[i];
        }

        while (true) {
            fill(dist.begin(), dist.end(), INFLL);
            vector<int> pv(n, -1), pe(n, -1);
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

            dist[s] = 0;
            pq.push({0, s});

            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d != dist[u]) continue;

                for (int i = 0; i < (int)adj[u].size(); i++) {
                    Edge &e = adj[u][i];
                    if (e.cap <= 0) continue;

                    ll nd = d + e.cost + pot[u] - pot[e.to];
                    if (dist[e.to] > nd) {
                        dist[e.to] = nd;
                        pv[e.to] = u;
                        pe[e.to] = i;
                        pq.push({nd, e.to});
                    }
                }
            }

            if (dist[t] == INFLL) break;

            for (int i = 0; i < n; i++) {
                if (dist[i] < INFLL) pot[i] += dist[i];
            }

            int add = (maxf == 0) ? INT_MAX : maxf;
            for (int v = t; v != s; v = pv[v]) {
                add = min(add, adj[pv[v]][pe[v]].cap);
            }
            if (maxf != 0 && flow + add > maxf) add = maxf - flow;

            for (int v = t; v != s; v = pv[v]) {
                Edge &e = adj[pv[v]][pe[v]];
                e.cap -= add;
                adj[v][e.rev].cap += add;
                cost += (ll)add * e.cost;
            }
            flow += add;

            if (maxf != 0 && flow == maxf) break;
        }
        return {flow, cost};
    }
};

// =====================================================================
// 3) MAX FLOW (DINIC)
//    Use when only maximum flow is needed (no costs).
//    Complexity: O(E * V^2) worst-case, but fast in practice.
// =====================================================================

struct Dinic {
    struct Edge {
        int to, rev, cap;
    };

    int n;
    vector<vector<Edge>> adj;
    vector<int> level, ptr;

    Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}

    void addEdge(int u, int v, int cap) {
        Edge a{v, (int)adj[v].size(), cap};
        Edge b{u, (int)adj[u].size(), 0};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : adj[u]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int t, int pushed) {
        if (pushed == 0) return 0;
        if (u == t) return pushed;
        for (int &cid = ptr[u]; cid < (int)adj[u].size(); cid++) {
            Edge &e = adj[u][cid];
            if (e.cap <= 0 || level[e.to] != level[u] + 1) continue;
            int tr = dfs(e.to, t, min(pushed, e.cap));
            if (tr == 0) continue;
            e.cap -= tr;
            adj[e.to][e.rev].cap += tr;
            return tr;
        }
        return 0;
    }

    int maxFlow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (int pushed = dfs(s, t, INT_MAX)) {
                flow += pushed;
            }
        }
        return flow;
    }
};

// =====================================================================
// 4) HUNGARIAN ALGORITHM (ASSIGNMENT PROBLEM)
//    Solves min-cost perfect matching for n rows and m columns (n <= m).
//    If n > m, it transposes the matrix (each column gets matched to a row).
//    Complexity: O(n^2 * m).
// =====================================================================

// Returns {minCost, assignment} where assignment[i] = column assigned to row i.
// If n > m, some rows may have assignment = -1 (meaning unmatched).
pair<ll, vector<int>> hungarian(const vector<vector<ll>> &a) {
    int n = (int)a.size();
    int m = (int)a[0].size();

    // If more rows than columns, transpose so that rows <= columns.
    if (n > m) {
        vector<vector<ll>> trans(m, vector<ll>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                trans[j][i] = a[i][j];
        auto res = hungarian(trans); // res.second has size m (original columns)
        vector<int> origAssign(n, -1);
        for (int j = 0; j < m; j++) {
            int row = res.second[j]; // original row matched to column j
            origAssign[row] = j;
        }
        return {res.first, origAssign};
    }

    // Standard Hungarian for n <= m
    vector<ll> u(n + 1), v(m + 1), p(m + 1), way(m + 1);
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(m + 1, INF);
        vector<bool> used(m + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0];
            ll delta = INF;
            int j1 = 0;
            for (int j = 1; j <= m; j++) {
                if (!used[j]) {
                    ll cur = a[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= m; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);

        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }

    vector<int> assignment(n);
    for (int j = 1; j <= m; j++) {
        if (p[j] > 0) assignment[p[j] - 1] = j - 1;
    }
    ll cost = -v[0];
    return {cost, assignment};
}

// =====================================================================
// 5) MIN-COST FLOW WITH LOWER BOUNDS
//    Some edges must carry at least 'low' units. Finds min-cost circulation
//    with an optional s-t flow requirement.
// =====================================================================

// edges: (u, v, low, high, cost)
// Returns {flowSent, totalCost}. If infeasible, returns {-1, -1}.
// 'flowSent' is the amount of flow on the t->s edge (i.e., the s-t flow).
pair<int, ll> minCostFlowWithLowerBounds(
    int n,
    vector<tuple<int, int, int, int, ll>> edges, // u, v, low, high, cost
    int s, int t,
    int req = 0          // required s-t flow; 0 means any
) {
    int SS = n, TT = n + 1;
    MCMF_Dijkstra mcmf(n + 2);

    vector<ll> demand(n, 0);
    ll baseCost = 0;

    // Add edges with adjusted capacities and accumulate demands
    for (auto &[u, v, low, high, cost] : edges) {
        demand[u] -= low;
        demand[v] += low;
        baseCost += low * cost;
        mcmf.addEdge(u, v, high - low, cost);
    }

    // Add t->s edge with capacity = req (or INF if req==0)
    int capTS = (req == 0) ? INT_MAX : req;
    int idxTS = (int)mcmf.adj[t].size(); // forward edge index in adj[t]
    mcmf.addEdge(t, s, capTS, 0);

    // Add super source/sink edges based on demands
    ll totalDemand = 0;
    for (int i = 0; i < n; i++) {
        if (demand[i] > 0) {
            mcmf.addEdge(SS, i, (int)demand[i], 0);
            totalDemand += demand[i];
        } else if (demand[i] < 0) {
            mcmf.addEdge(i, TT, (int)(-demand[i]), 0);
        }
    }

    // Run MCMF from SS to TT, send as much as possible
    auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, 0);

    if (flow != totalDemand) {
        return {-1, -1}; // infeasible
    }

    // Compute actual flow on t->s edge
    int flowOnTS = capTS - mcmf.adj[t][idxTS].cap;
    return {flowOnTS, cost + baseCost};
}

// =====================================================================
// 6) HELPER FUNCTIONS FOR COMMON PATTERNS
// =====================================================================

// 6.1) MIN-COST FLOW WITH VERTEX CAPACITIES (NODE SPLITTING)
//      Each node can handle at most vertexCap[i] units of flow.
//      If vertexCap[i] == 0, it means infinite.
//      Returns {flow, cost}.
pair<int, ll> minCostFlowWithVertexCaps(
    int n,
    vector<tuple<int, int, int, ll>> edges, // (u, v, cap, cost)
    vector<int> vertexCap,                  // size n
    int s, int t,
    int maxFlow = 0
) {
    int N = 2 * n + 2;
    int SS = 2 * n;
    int TT = 2 * n + 1;
    MCMF_Dijkstra mcmf(N);

    // Vertex capacity edges: in(v) -> out(v)
    for (int v = 0; v < n; v++) {
        int cap = (vertexCap[v] == 0) ? INT_MAX / 2 : vertexCap[v];
        mcmf.addEdge(2 * v, 2 * v + 1, cap, 0);
    }

    // Original edges: out(u) -> in(v)
    for (auto &[u, v, cap, cost] : edges) {
        mcmf.addEdge(2 * u + 1, 2 * v, cap, cost);
    }

    // Super source -> s_in, t_out -> super sink
    int req = (maxFlow == 0) ? INT_MAX / 2 : maxFlow;
    mcmf.addEdge(SS, 2 * s, req, 0);
    mcmf.addEdge(2 * t + 1, TT, req, 0);

    auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, maxFlow);
    return {flow, cost};
}

// 6.2) MULTI-SOURCE / MULTI-SINK MIN-COST FLOW
//      Sources have supplies, sinks have demands.
//      Returns {flow, cost}.
pair<int, ll> multiSourceSinkMCMF(
    int n,
    vector<tuple<int, int, int, ll>> edges,
    vector<pair<int, int>> sources, // (node, supply)
    vector<pair<int, int>> sinks,   // (node, demand)
    int maxFlow = 0
) {
    int SS = n, TT = n + 1;
    MCMF_Dijkstra mcmf(n + 2);

    for (auto &[u, v, cap, cost] : edges) {
        mcmf.addEdge(u, v, cap, cost);
    }

    ll totalSupply = 0;
    for (auto &[node, supply] : sources) {
        mcmf.addEdge(SS, node, supply, 0);
        totalSupply += supply;
    }

    ll totalDemand = 0;
    for (auto &[node, demand] : sinks) {
        mcmf.addEdge(node, TT, demand, 0);
        totalDemand += demand;
    }

    int req = (maxFlow == 0) ? (int)min(totalSupply, totalDemand) : maxFlow;
    auto [flow, cost] = mcmf.minCostMaxFlow(SS, TT, req);
    return {flow, cost};
}

// 6.3) MAX PROFIT FLOW (negate profits and run MCMF)
pair<int, ll> maxProfitFlow(
    int n,
    vector<tuple<int, int, int, ll>> edges, // (u, v, cap, profit)
    int s, int t,
    int maxFlow = 0
) {
    vector<tuple<int, int, int, ll>> costEdges;
    for (auto &[u, v, cap, profit] : edges) {
        costEdges.emplace_back(u, v, cap, -profit);
    }
    MCMF_Dijkstra mcmf(n);
    for (auto &[u, v, cap, cost] : costEdges) {
        mcmf.addEdge(u, v, cap, cost);
    }
    auto [flow, minCost] = mcmf.minCostMaxFlow(s, t, maxFlow);
    return {flow, -minCost};
}

// 6.4) MAXIMUM WEIGHT BIPARTITE MATCHING (dense)
//      Uses Hungarian after negating profits.
//      Returns {maxProfit, assignment} (assignment may have -1 for unmatched rows).
pair<ll, vector<int>> maxWeightBipartiteMatching(const vector<vector<ll>>& profitMatrix) {
    int n = profitMatrix.size();
    int m = profitMatrix[0].size();
    vector<vector<ll>> costMatrix(n, vector<ll>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            costMatrix[i][j] = -profitMatrix[i][j];
    auto [minCost, assignment] = hungarian(costMatrix);
    return {-minCost, assignment};
}

// 6.5) MINIMUM PATH COVER IN A DAG (unweighted)
//      Returns the minimum number of vertex-disjoint paths covering all nodes.
int minPathCoverCount(int n, const vector<pair<int, int>>& dagEdges) {
    int total = 2 * n + 2;
    int S = 2 * n, T = 2 * n + 1;
    Dinic dinic(total);

    for (int i = 0; i < n; i++) {
        dinic.addEdge(S, i, 1);
        dinic.addEdge(n + i, T, 1);
    }
    for (auto &[u, v] : dagEdges) {
        dinic.addEdge(u, n + v, 1);
    }

    int maxMatching = dinic.maxFlow(S, T);
    return n - maxMatching;
}

// 6.6) MINIMUM COST PATH COVER IN A DAG (weighted)
//      Returns {numberOfPaths, minTotalCost}.
pair<int, ll> minCostPathCover(int n, const vector<tuple<int, int, ll>>& dagEdges) {
    int S = 2 * n, T = 2 * n + 1;
    MCMF_Dijkstra mcmf(2 * n + 2);

    for (int i = 0; i < n; i++) {
        mcmf.addEdge(S, i, 1, 0);
        mcmf.addEdge(n + i, T, 1, 0);
    }
    for (auto &[u, v, cost] : dagEdges) {
        mcmf.addEdge(u, n + v, 1, cost);
    }

    auto [flow, cost] = mcmf.minCostMaxFlow(S, T, 0);
    int paths = n - flow;
    return {paths, cost};
}

// =====================================================================
// EXAMPLE USAGE (remove in production)
// =====================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example 1: Basic MCMF (SPFA)
    MCMF_SPFA mcmf1(4);
    mcmf1.addEdge(0, 1, 10, 2);
    mcmf1.addEdge(0, 2, 10, 3);
    mcmf1.addEdge(1, 3, 5, 1);
    mcmf1.addEdge(2, 3, 10, 4);
    auto res1 = mcmf1.minCostMaxFlow(0, 3);
    cout << "SPFA MCMF: Flow=" << res1.first << ", Cost=" << res1.second << "\n";

    // Example 2: Hungarian
    vector<vector<ll>> costMatrix = {
        {4, 1, 3},
        {2, 0, 5},
        {3, 2, 2}
    };
    auto res2 = hungarian(costMatrix);
    cout << "Hungarian: Min Cost=" << res2.first << "\nAssignment: ";
    for (int x : res2.second) cout << x << " ";
    cout << "\n";

    // Example 3: Dinic max flow
    Dinic dinic(4);
    dinic.addEdge(0, 1, 10);
    dinic.addEdge(0, 2, 10);
    dinic.addEdge(1, 3, 5);
    dinic.addEdge(2, 3, 10);
    cout << "Dinic Max Flow: " << dinic.maxFlow(0, 3) << "\n";

    return 0;
}