struct MCMF{
    struct Edge{
        int from, to, rev;
        ll cost, cap, flow;

        Edge(int _from, int _to, ll _cap, ll _cost,int _rev){
            from = _from, to = _to, cap = _cap, cost = _cost, rev = _rev;
            flow = 0;
        }

        bool operator < (const Edge &e) const{
            return cost < e.cost;
        }
    };

    int n;
    vector<vector<Edge>> adj;
    const ll INF = 1e16;

    MCMF(int _n){
        n = _n+2;
        adj = vector<vector<Edge>>(n);
    }

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

    pair<ll,ll> minCostMaxFlow(int s,int t){
        ll maxFlow = 0, cost = 0;

        while(true){
            vector<pair<ll,ll>> path = spfa(s,t);
            if(path.empty()) break;

            ll newFlow = INF;
            for(auto &it: path){
                Edge &e = adj[it.first][it.second];
                newFlow = min(newFlow,e.cap - e.flow);
            }

            for(auto&it : path){
                Edge &e = adj[it.first][it.second];
                e.flow += newFlow;
                cost += e.cost * newFlow;
                adj[e.to][e.rev].flow -= newFlow;
            }
            maxFlow += newFlow;
        }

        return {maxFlow,cost};
    }


    enum visit {unvisited, inqueue, visited};

    vector<pair<ll,ll>> spfa(int s,int t){
        vector<int> dist(n,INF),prev(n,-1),from_edge(n),state(n,unvisited);
        queue<int> q;
        dist[s] = 0;
        q.push(s);


        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i = 0; i < adj[u].size(); i++){
                Edge e = adj[u][i];
                if(e.flow >= e.cap || dist[e.to] <= dist[u] + e.cost) continue;

                dist[e.to] = dist[u] + e.cost;
                prev[e.to] = u;
                from_edge[e.to] = i;

                if(state[e.to] == inqueue) continue;
                if(state[e.to] == visited || (!q.empty() and dist[q.front()] > dist[e.to])){
                    q.push(e.to);
                }else{
                    q.push(e.to);
                }
                state[e.to] = inqueue;
            }
        }


        if(dist[t] == INF) return {};
        if(dist[t] > 0) return {};
        vector<pair<ll,ll>> path;
        int cur = t;
        while(cur != s){
            path.push_back({prev[cur],from_edge[cur]});
            cur = prev[cur];
        }


        reverse(path.begin(),path.end());
        return path;
    }

};