//
// フローアルゴリズム ほぼ全集
//


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


// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }


//------------------------------//
// Flow
//------------------------------//

// edge class (for max-flow)
template<class FLOW> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOW cap, icap, flow;
    
    // constructor
    constexpr FlowEdge() noexcept = default;
    constexpr FlowEdge(int rev, int from, int to, FLOW cap, FLOW rcap = 0) 
        : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap) {
    }
    void reset() { 
        flow -= icap - cap;
        cap = icap;
    }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& e) {
        return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.flow << ")";
    }
};

// graph class (for max-flow)
template<class FLOW> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOW>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.clear(), list.resize(n);
        pos.clear();
    }
    void resize(int n) {
        list.resize(n);
    }
    void clear() {
        list.clear(), pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOW>> &operator [] (int i) {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    const vector<FlowEdge<FLOW>> &operator [] (int i) const {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    size_t size() const noexcept {
        return list.size();
    }
    size_t size_edegs() const noexcept {
        return pos.size();
    }
    FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) {
        return list[e.to][e.rev];
    }
    const FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) const {
        return list[e.to][e.rev];
    }
    FlowEdge<FLOW> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOW> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOW>> get_edges() const {
        vector<FlowEdge<FLOW>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() const {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOW> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOW> &e, FLOW new_cap, FLOW new_rcap) {
        assert(new_cap >= 0 && new_rcap >= 0);
        FlowEdge<FLOW> &re = get_rev_edge(e);
        e.cap = new_cap, e.icap = new_cap + new_rcap, e.flow = new_rcap;
        re.cap = new_rcap, re.icap = new_cap + new_rcap, re.flow = new_cap;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOW cap, FLOW rcap = 0) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        int from_id = int(list[from].size()), to_id = int(list[to].size());
        if (from == to) to_id++;
        pos.emplace_back(from, from_id);
        list[from].push_back(FlowEdge<FLOW>(to_id, from, to, cap, rcap));
        list[to].push_back(FlowEdge<FLOW>(from_id, to, from, rcap, cap));
    }
    void add_bidirected_edge(int from, int to, FLOW cap) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        add_edge(from, to, cap, cap);
    }

    // augment
    FLOW augment(int s, int t, FLOW up_flow = numeric_limits<FLOW>::max()) {
        vector<bool> seen(size(), false);
        auto dfs = [&](auto &&dfs, int v, FLOW up_flow) -> FLOW {
            if (v == t) return up_flow;
            seen[v] = true;
            for (int i = 0; i < (int)list[v].size(); i++) {
                FlowEdge<FLOW> &e = list[v][i], &re = get_rev_edge(e);
                if (seen[e.to] || e.cap <= 0) continue;
                FLOW flow = dfs(dfs, e.to, min(up_flow, e.cap));
                if (flow > 0) {
                    e.cap -= flow, e.flow += flow;
                    re.cap += flow, re.flow -= flow;
                    return flow;
                }
            }  
            return FLOW(0); 
        };
        return dfs(dfs, s, up_flow);
    };
    FLOW augment(int s, int t, vector<FlowEdge<FLOW>> &path, FLOW up_flow = numeric_limits<FLOW>::max()) {
        vector<bool> seen(size(), false);
        auto dfs = [&](auto &&dfs, int v, vector<FlowEdge<FLOW>> &path, FLOW up_flow) -> FLOW {
            if (v == t) return up_flow;
            seen[v] = true;
            for (int i = 0; i < (int)list[v].size(); i++) {
                FlowEdge<FLOW> &e = list[v][i], &re = get_rev_edge(e);
                if (seen[e.to] || e.cap <= 0) continue;
                FLOW flow = dfs(dfs, e.to, path, min(up_flow, e.cap));
                if (flow > 0) {
                    e.cap -= flow, e.flow += flow;
                    re.cap += flow, re.flow -= flow;
                    path.emplace_back(e);
                    return flow;
                }
            }  
            return FLOW(0); 
        };
        path.clear();
        FLOW res = dfs(dfs, s, path, up_flow);
        reverse(path.begin(), path.end());
        return res;
    };

    // find reachable nodes from node s (1: s-domain, -1: t-domain, 0: no reach)
    vector<int> find_cut(int s, int t) const {
        vector<int> res(size(), 0);
        auto dfs_s = [&](auto &&dfs_s, int v) -> void {
            res[v] = 1;
            for (const auto &e : list[v]) {
                if (res[e.to] || e.cap <= 0) continue;
                dfs_s(dfs_s, e.to);
            }
        };
        auto dfs_t = [&](auto &&dfs_t, int v) -> void {
            res[v] = -1;
            for (const auto &e : list[v]) {
                auto re = get_rev_edge(e);
                if (res[e.to] || re.cap <= 0) continue;
                dfs_t(dfs_t, e.to);
            }
        };
        dfs_s(dfs_s, s), dfs_t(dfs_t, t);
        return res;
    }

    // finc cutset
    vector<FlowEdge<FLOW>> find_cutset(int s, int t) const {
        vector<int> cut = find_cut(s, t);
        vector<FlowEdge<FLOW>> res;
        const auto &edges = get_edges();
        for (const auto &e : edges) {
            if (cut[e.from] == 1 && cut[e.to] != 1) {
                res.emplace_back(e);
            }
        }
        return res;
    }

    // check if the s-t flow is feasible
    bool is_feasible(int s, int t) const {
        vector<FLOW> b(list.size(), FLOW(0));
        for (int v = 0; v < (int)list.size(); v++) {
            for (const auto &e : list[v]) {
                b[v] += (e.flow - get_rev_edge(e).flow) / 2;
            }
        }
        if (b[s] + b[t] != 0) return false;
        for (int v = 0; v < (int)list.size(); v++) {
            if (v != s && v != t && b[v] != FLOW(0)) return false;
        }
        return true;
    }
    bool is_feasible(int s, int t, FLOW flow) const {
        vector<FLOW> b(list.size(), FLOW(0));
        for (int v = 0; v < (int)list.size(); v++) {
            for (const auto &e : list[v]) {
                b[v] += (e.flow - get_rev_edge(e).flow) / 2;
            }
        }
        if (b[s] != flow) return false;
        if (b[t] != -flow) return false;
        for (int v = 0; v < (int)list.size(); v++) {
            if (v != s && v != t && b[v] != FLOW(0)) return false;
        }
        return true;
    }

    // decompose flow into s-t simple paths and cycles
    using Path = vector<FlowEdge<FLOW>>;
    pair<vector<Path>, vector<Path>> decompose(int s, int t) const {
        struct Arc {
            int to;
            FLOW rem;
            int eidx;
        };
        assert(is_feasible(s, t));
        vector<vector<Arc>> fg(list.size());
        for (int v = 0; v < (int)list.size(); v++) {
            for (int j = 0; j < (int)list[v].size(); j++) {
                FLOW f = list[v][j].icap - list[v][j].cap;
                if (f > 0) fg[v].push_back({list[v][j].to, f, j});
            }
        }
        vector<int> ptr(list.size(), 0), onpath(list.size(), -1);
        vector<pair<int, int>> route;
        vector<int> used;
        vector<Path> paths, cycles;

        auto next_arc = [&](int v) -> int {
            while (ptr[v] < (int)fg[v].size() && fg[v][ptr[v]].rem <= 0) ptr[v]++;
            return (ptr[v] < (int)fg[v].size() ? ptr[v] : -1);
        };
        auto extract = [&](int begin, bool is_cycle) {
            FLOW mi = numeric_limits<FLOW>::max();
            for (int k = begin; k < (int)route.size(); k++) {
                auto [v, i] = route[k];
                mi = min(mi, fg[v][i].rem);
            }
            vector<FlowEdge<FLOW>> seq;
            for (int k = begin; k < (int)route.size(); k++) {
                auto [v, i] = route[k];
                fg[v][i].rem -= mi;
                FlowEdge<FLOW> e = list[v][fg[v][i].eidx];
                e.flow = mi;
                seq.push_back(e);
            }
            if (is_cycle) cycles.push_back(std::move(seq));
            else paths.push_back(std::move(seq));
        };
        auto walk = [&](int start, bool stop_at_t) {
            route.clear();
            int v = start;
            onpath[v] = 0;
            used.push_back(v);
            while (true) {
                int i = next_arc(v), u = fg[v][i].to;
                route.push_back({v, i});
                if (stop_at_t && u == t) {
                    extract(0, false);
                    break;
                }
                if (onpath[u] != -1) {
                    extract(onpath[u], true);
                    break;
                }
                onpath[u] = (int)route.size();
                used.push_back(u);
                v = u;
            }
            for (int w : used) onpath[w] = -1;
            used.clear();
        };

        // extract all s-t paths
        while (next_arc(s) != -1) walk(s, true);

        // decompose remained circulation into cycles
        for (int v = 0; v < (int)list.size(); v++) while (next_arc(v) != -1) walk(v, false);

        return {paths, cycles};
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// Dinic
template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t, FLOW limit_flow) {
    assert(0 <= s && s < G.size() && 0 <= t && t < G.size() && s != t);
    FLOW current_flow = 0;
    vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
    
    // Dinic BFS
    auto bfs = [&]() -> void {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const FlowEdge<FLOW> &e : G[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        }
    };
    
    // Dinic DFS
    auto dfs = [&](auto self, int v, FLOW up_flow) {
        if (v == t) return up_flow;
        FLOW res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOW> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap <= 0) continue;
            FLOW flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        bfs();
        if (level[t] < 0) break;
        iter.assign((int)iter.size(), 0);
        while (current_flow < limit_flow) {
            FLOW flow = dfs(dfs, s, limit_flow - current_flow);
            if (flow <= 0) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t) {
    return Dinic(G, s, t, numeric_limits<FLOW>::max());
}

// edge class (for min-cost flow)
template<class FLOW, class COST> struct FlowCostEdge {
    // core members
    int rev, from, to;
    FLOW cap, icap, flow;
    COST cost;
    
    // constructor
    constexpr FlowCostEdge() noexcept = default;
    constexpr FlowCostEdge(int rev, int from, int to, FLOW cap, COST cost)
        : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(0), cost(cost) {
    }
    constexpr FlowCostEdge(int rev, int from, int to, FLOW cap, FLOW rcap, COST cost)
        : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap), cost(cost) {
    }
    void reset() { 
        flow -= icap - cap;
        cap = icap;
    }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowCostEdge& e) {
        return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.flow << ", " << e.cost << ")";
    }
};

// graph class (for min-cost flow)
template<class FLOW, class COST> struct FlowCostGraph {
    // core members
    vector<vector<FlowCostEdge<FLOW, COST>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    vector<COST> pot;  // pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
    bool include_negative_edge = false;
    
    // constructor
    FlowCostGraph(int n = 0) : list(n), pot(n), include_negative_edge(false) { }
    void init(int n = 0) {
        list.clear(), list.resize(n);
        pos.clear();
        pot.assign(n, 0);
        include_negative_edge = false;
    }
    
    // getter
    vector<FlowCostEdge<FLOW, COST>> &operator [] (int i) {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    const vector<FlowCostEdge<FLOW, COST>> &operator [] (int i) const {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    size_t size() const noexcept {
        return list.size();
    }
    size_t size_edegs() const noexcept {
        return pos.size();
    }
    FlowCostEdge<FLOW, COST> &get_rev_edge(const FlowCostEdge<FLOW, COST> &e) {
        return list[e.to][e.rev];
    }
    const FlowCostEdge<FLOW, COST> &get_rev_edge(const FlowCostEdge<FLOW, COST> &e) const {
        return list[e.to][e.rev];
    }
    FlowCostEdge<FLOW, COST> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowCostEdge<FLOW, COST> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowCostEdge<FLOW, COST>> get_edges() const {
        vector<FlowCostEdge<FLOW, COST>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowCostEdge<FLOW, COST> &e : list[i]) e.reset();
        }
    }
    
    // add_edge
    void add_edge(int from, int to, FLOW cap, COST cost) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        int from_id = (int)list[from].size(), to_id = (int)list[to].size();
        if (from == to) to_id++;
        pos.emplace_back(from, from_id);
        list[from].push_back(FlowCostEdge<FLOW, COST>(to_id, from, to, cap, 0, cost));
        list[to].push_back(FlowCostEdge<FLOW, COST>(from_id, to, from, 0, cap, -cost));
        if (cost < 0) include_negative_edge = true;
    }
    void add_edge(int from, int to, FLOW cap, FLOW rcap, COST cost) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        int from_id = (int)list[from].size(), to_id = (int)list[to].size();
        if (from == to) to_id++;
        pos.emplace_back(from, from_id);
        list[from].push_back(FlowCostEdge<FLOW, COST>(to_id, from, to, cap, rcap, cost));
        list[to].push_back(FlowCostEdge<FLOW, COST>(from_id, to, from, rcap, cap, -cost));
        if (cost < 0) include_negative_edge = true;
    }
    void add_bidirected_edge(int from, int to, FLOW cap, COST cost) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        add_edge(from, to, cap, cap, cost);
    }

    // find initial potential (to resolve initial negative-edge)
    // pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
    bool calc_potential_dag() {
        pot.assign(size(), 0);
        vector<int> deg(size(), 0), st;
        for (int v = 0; v < (int)size(); v++) for (const auto &e : list[v]) deg[e.to] += (e.cap > 0);
        st.reserve(size());
        for (int v = 0; v < (int)size(); v++) if (!deg[v]) st.emplace_back(v);
        for (int i = 0; i < (int)size(); i++) {
            if ((int)st.size() == i) return false;  // not DAG
            int cur = st[i];
            for (const auto &e : list[cur]) {
                if (e.cap <= 0) continue;
                deg[e.to]--;
                if (deg[e.to] == 0) st.emplace_back(e.to);
                if (pot[e.to] >= pot[cur] + e.cost) pot[e.to] = pot[cur] + e.cost;
            }
        }
        return true;
    }
    bool calc_potential_spfa() {
        pot.assign(size(), 0);
        queue<int> que;
        vector<bool> inque(size(), false);
        vector<int> cnt(size(), 0);
        for (int v = 0; v < (int)size(); v++) que.push(v), inque[v] = true;
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            inque[cur] = false;
            if (cnt[cur] > (int)size()) return false;  // include negative-cycle
            cnt[cur]++;
            for (const auto &e : list[cur]) {
                if (e.cap <= 0) continue;
                if (pot[e.to] > pot[cur] + e.cost) {
                    pot[e.to] = pot[cur] + e.cost;
                    if (!inque[e.to]) inque[e.to] = true, que.push(e.to);
                }
            }
        }
        return true;
    }
    bool calc_potential() {
        return calc_potential_dag() || calc_potential_spfa();
    }
    bool init_potential() {
        if (!include_negative_edge) return true;
        return calc_potential();
    }

    // decompose flow into s-t simple paths and cycles
    using Path = vector<FlowCostEdge<FLOW, COST>>;
    pair<vector<Path>, vector<Path>> decompose(int s, int t) const {
        struct Arc {
            int to;
            FLOW rem;
            int eidx;
        };
        vector<vector<Arc>> fg(list.size());
        for (int v = 0; v < (int)list.size(); v++) {
            for (int j = 0; j < (int)list[v].size(); j++) {
                FLOW f = list[v][j].icap - list[v][j].cap;
                if (f > 0) fg[v].push_back({list[v][j].to, f, j});
            }
        }
        vector<Path> paths, cycles;

        auto build = [&](const vector<pair<int,int>> &route, bool is_cycle) {
            FLOW mi = numeric_limits<FLOW>::max();
            for (auto [v,i] : route) mi = min(mi, fg[v][i].rem);
            vector<FlowCostEdge<FLOW,COST>> seq;
            for (auto [v,i] : route) {
                fg[v][i].rem -= mi;
                FlowCostEdge<FLOW,COST> e = list[v][fg[v][i].eidx];
                e.flow = mi;
                seq.push_back(e);
            }
            if (is_cycle) cycles.push_back(std::move(seq));
            else paths.push_back(std::move(seq));
        };

        // Phase 1: extract all cycles and make graph DAG
        const int NOTSEEN = 0, INSTACK = 1, FINISH = 2;
        vector<int> color(list.size(), NOTSEEN);
        vector<int> pos_in_stack(list.size(), -1);
        vector<pair<int, int>> stk;
        auto dfs = [&](auto &&dfs, int v) -> bool {
            color[v] = INSTACK;
            pos_in_stack[v] = (int)stk.size();
            for (int i = 0; i < (int)fg[v].size(); i++) {
                if (fg[v][i].rem <= 0) continue;
                int u = fg[v][i].to;
                if (color[u] == INSTACK) {
                    vector<pair<int,int>> route;
                    for (int k = pos_in_stack[u]; k < (int)stk.size(); k++) {
                        route.push_back(stk[k]);
                    }
                    route.push_back({v, i});
                    build(route, true);
                    return true;
                }
                if (color[u] == NOTSEEN) {
                    stk.push_back({v, i});
                    if (dfs(dfs, u)) return true;
                    stk.pop_back();
                }
            }
            color[v] = FINISH;
            pos_in_stack[v] = -1;
            return false;
        };
        while (true) {
            fill(color.begin(), color.end(), NOTSEEN);
            stk.clear();
            bool found = false;
            for (int v = 0; v < (int)list.size() && !found; v++) {
                if (color[v] == NOTSEEN && dfs(dfs, v)) found = true;
            }
            if (!found) break;
        }

        // Phase 2: find all s-t paths
        vector<int> ptr(list.size(), 0);
        auto next_arc = [&](int v) -> int {
            while (ptr[v] < (int)fg[v].size() && fg[v][ptr[v]].rem <= 0) ptr[v]++;
            return ptr[v] < (int)fg[v].size() ? ptr[v] : -1;
        };
        while (next_arc(s) != -1) {
            vector<pair<int,int>> route;
            int v = s;
            while (v != t) {
                int i = next_arc(v);
                route.push_back({v, i});
                v = fg[v][i].to;
            }
            build(route, false);
        }
        return {paths, cycles};
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowCostGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// min-cost max-flow (<= limit_flow), slope ver.
template<class FLOW, class COST> vector<pair<FLOW, COST>>
MinCostFlowSlope(FlowCostGraph<FLOW, COST> &G, int S, int T, FLOW limit_flow)
{
    // result values
    FLOW cur_flow = 0;
    COST cur_cost = 0, pre_cost = numeric_limits<COST>::max() / 2;
    vector<pair<FLOW, COST>> res;
    res.emplace_back(cur_flow, cur_cost);
    
    // intermediate values
    vector<COST> dist((int)G.size(), numeric_limits<COST>::max() / 2);
    vector<int> prevv((int)G.size(), -1), preve((int)G.size(), -1);
    
    // dual
    auto dual_step = [&]() -> bool {
        dist.assign((int)G.size(), numeric_limits<COST>::max() / 2);
        dist[S] = 0;
        priority_queue<pair<COST,int>, vector<pair<COST,int>>, greater<pair<COST,int>>> que;
        que.emplace(0, S);
        while (!que.empty()) {
            auto [cur, v] = que.top();
            que.pop();
            if (cur > dist[v]) continue;
            for (int i = 0; i < (int)G[v].size(); i++) {
                const auto &e = G[v][i];
                COST add = e.cost + G.pot[v] - G.pot[e.to];
                if (e.cap > 0 && dist[e.to] > dist[v] + add) {
                    dist[e.to] = dist[v] + add;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
        return dist[T] < numeric_limits<COST>::max() / 2;
    };
    
    // primal
    auto primal_step = [&]() -> void {
        for (int v = 0; v < G.size(); v++) {
            if (dist[v] < numeric_limits<COST>::max() / 2) G.pot[v] += dist[v];
            else G.pot[v] = numeric_limits<COST>::max() / 2;
        }
        FLOW flow = limit_flow - cur_flow;
        COST cost = G.pot[T] - G.pot[S];
        for (int v = T; v != S; v = prevv[v]) {
            flow = min(flow, G[prevv[v]][preve[v]].cap);
        }
        for (int v = T; v != S; v = prevv[v]) {
            FlowCostEdge<FLOW, COST> &e = G[prevv[v]][preve[v]];
            FlowCostEdge<FLOW, COST> &re = G.get_rev_edge(e);
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
        }
        cur_flow += flow;
        cur_cost += flow * cost;
        if (pre_cost == cost) res.pop_back();
        res.emplace_back(cur_flow, cur_cost);
        pre_cost = cost;
    };

    // initialize potential
    assert(G.init_potential());
    
    // primal-dual
    while (cur_flow < limit_flow) {
        if (!dual_step()) break;
        primal_step();
    }
    return res;
}

// min-cost max-flow, slope ver.
template<class FLOW, class COST> vector<pair<FLOW, COST>>
MinCostFlowSlope(FlowCostGraph<FLOW, COST> &G, int S, int T)
{
    return MinCostFlowSlope(G, S, T, numeric_limits<FLOW>::max());
}

// min-cost max-flow (<= limit_flow)
template<class FLOW, class COST> pair<FLOW, COST>
MinCostFlow(FlowCostGraph<FLOW, COST> &G, int S, int T, FLOW limit_flow)
{
    return MinCostFlowSlope(G, S, T, limit_flow).back();
}

// min-cost max-flow (<= limit_flow)
template<class FLOW, class COST> pair<FLOW, COST>
MinCostFlow(FlowCostGraph<FLOW, COST> &G, int S, int T)
{
    return MinCostFlow(G, S, T, numeric_limits<FLOW>::max());
}

// Min Cost Circulation Flow by Cost-Scaling 
template<class FLOW, class COST> COST MinCostCirculation(FlowCostGraph<FLOW, COST> &G) {
    const int N = (int)G.size();
    const COST SCALE = N + 1;
    COST eps = 1;
    vector<FLOW> balance(G.size(), 0);
    vector<COST> price(G.size(), 0);
    
    auto reduced_cost = [&](const FlowCostEdge<FLOW, COST> &e) -> COST {
        return e.cost * SCALE - price[e.from] + price[e.to];
    };

    auto ConstructGaux = [&]() -> void {
        vector<bool> visited(G.size(), false);
        vector<int> st;
        st.reserve(N);
        for (int s = 0; s < N; s++) {
            if (balance[s] <= 0 || visited[s]) continue;
            visited[s] = true;
            st.push_back(s);
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                for (const auto &e : G[v]) {
                    if (e.cap <= 0 || reduced_cost(e) >= 0 || visited[e.to]) continue;
                    visited[e.to] = true;
                    st.push_back(e.to);
                }
            }
        }
        for (int v = 0; v < G.size(); ++v) if (visited[v]) price[v] += eps;
    };

    auto augment_blocking_flow = [&]() -> bool {
        vector<int> iter(N, 0);
        auto augment = [&](auto &&augment, int v, FLOW flow) -> FLOW {
            if (balance[v] < 0) {
                FLOW dif = min(flow, -balance[v]);
                balance[v] += dif;
                return dif;
            }
            for (int &i = iter[v]; i < (int)G[v].size(); i++) {
                auto &e = G[v][i];
                if (e.cap <= 0 || reduced_cost(e) >= 0) continue;
                FLOW dif = augment(augment, e.to, min(flow, e.cap));
                if (dif <= 0) continue;
                auto &re = G.get_rev_edge(e);
                e.cap -= dif, e.flow += dif;
                re.cap += dif, re.flow -= dif;
                return dif;
            }
            return FLOW(0);
        };
        bool finish = true;
        for (int v = 0; v < N; ++v) {
            while (balance[v] > 0) {
                FLOW f = augment(augment, v, balance[v]);
                if (f <= 0) break;
                balance[v] -= f;
            }
            if (balance[v] > 0) finish = false;
        }
        return finish;
    };

    // eps init
    COST need = 0;
    for (int v = 0; v < N; v++) {
        for (const auto &e : G[v]) {
            if (e.cap <= 0) continue;
            need = max(need, -e.cost * SCALE);
        }
    }
    while (eps < need) eps *= 2;

    // cost scaling
    while (eps > 1) {
        eps /= 2;
        for (int v = 0; v < N; v++) {
            for (int i = 0; i < (int)G[v].size(); i++) {
                auto &e = G[v][i];
                if (e.cap <= 0 || reduced_cost(e) >= 0) continue;
                auto &re = G.get_rev_edge(e);
                FLOW f = e.cap;
                balance[e.from] -= f, balance[e.to] += f;
                e.cap -= f, e.flow += f;
                re.cap += f, re.flow -= f;
            }
        }
        while (true) {
            ConstructGaux();
            if (augment_blocking_flow()) break;
        }
    }
    COST res = 0;
    const auto &edges = G.get_edges();
    for (const auto &e : edges) res += e.flow * e.cost;
    return res;
}


//--------------------------------//
// Minumum Cost b-flow
//--------------------------------//

// Minimum Cost b-flow (by primal-dual, negative cycle is NG)
template<class FLOW, class COST> struct MinCostBFlowByPrimalDual {
    // inner values
    int N;
    FlowCostGraph<FLOW, COST> G;
    vector<FLOW> dss;  // demand (< 0) and supply (> 0)
    vector<COST> dual;

    // constructor
    explicit MinCostBFlowByPrimalDual(int n) : N(n), G(n + 2), dss(n, 0) {}

    // setter
    void add_edge(int from, int to, FLOW cap, COST cost) {
        assert(cap >= 0);
        G.add_edge(from, to, cap, cost);
    }
    void set_ds(int v, FLOW ds) {
        assert(0 <= v && v < N);
        dss[v] = ds;
    }
    void set_ds(const vector<FLOW> &vds) {
        assert((int)vds.size() == N);
        dss = vds;
    }

    // getter
    FlowCostEdge<FLOW, COST> &get_edge(int i) {
        return G.get_edge(i);
    }
    const FlowCostEdge<FLOW, COST> &get_edge(int i) const {
        return G.get_edge(i);
    }
    vector<FlowCostEdge<FLOW, COST>> get_edges() const {
        return G.get_edges();
    }
    COST get_dual(int v) const {
        return dual[v];
    }
    vector<COST> get_duals() const {
        return dual;
    }

    // solver
    pair<bool, COST> solve(bool calc_potential = false) {
        // dss treatment
        int s = N, t = N + 1;
        FLOW ssum = 0, tsum = 0;
        for (int v = 0; v < N; v++) {
            if (dss[v] > 0) ssum += dss[v], G.add_edge(s, v, dss[v], COST(0));
            else if (dss[v] < 0) tsum -= dss[v], G.add_edge(v, t, -dss[v], COST(0));
        }

        // feasibility check
        if (ssum != tsum) return {false, COST(0)};
        
        // min-cost flow
        auto [maxflow, mincost] = MinCostFlow(G, s, t, ssum);
        if (maxflow < ssum) return {false, COST(0)};

        // find dual
        if (calc_potential) {
            G.calc_potential();
            dual = G.pot;
            dual.pop_back(), dual.pop_back();  // eliminate s, t
        }
        return {true, mincost};
    }
};

// Minimum Cost b-flow (by cost-scaling min-cost circulation)
template<class FLOW, class COST> struct MinCostBFlowByCostScaling {
    // inner Edge
    struct InnerEdge {
        int from, to;
        FLOW cap;
        COST cost;
        InnerEdge(int from_, int to_, FLOW cap_, COST cost_) : from(from_), to(to_), cap(cap_), cost(cost_) {}
        friend ostream& operator << (ostream& s, const InnerEdge& e) {
            return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.cost << ")";
        }
    };

    // inner values
    int N;
    FlowCostGraph<FLOW, COST> G;
    vector<InnerEdge> edges;
    vector<FLOW> dss;  // demand (< 0) and supply (> 0)
    vector<COST> dual;

    // constructor
    explicit MinCostBFlowByCostScaling(int n = 0) : N(n), G(n), dss(n, 0) {}

    // setter
    void add_edge(int from, int to, FLOW cap, COST cost) {
        assert(cap >= 0);
        edges.push_back(InnerEdge(from, to, cap, cost));
    }
    void set_ds(int v, FLOW ds) {
        assert(0 <= v && v < N);
        dss[v] = ds;
    }
    void set_ds(const vector<FLOW> &vds) {
        assert((int)vds.size() == N);
        dss = vds;
    }

    // getter
    FlowCostEdge<FLOW, COST> &get_edge(int i) {
        return G.get_edge(i);
    }
    const FlowCostEdge<FLOW, COST> &get_edge(int i) const {
        return G.get_edge(i);
    }
    vector<FlowCostEdge<FLOW, COST>> get_edges() const {
        return G.get_edges();
    }
    COST get_dual(int v) const {
        return dual[v];
    }
    vector<COST> get_duals() const {
        return dual;
    }

    // solver
    pair<bool, COST> solve(bool calc_potential = true) {
        // push s-t flow
        FlowGraph<FLOW> preG(N + 2);
        int s = N, t = N + 1;
        for (const auto &e : edges) preG.add_edge(e.from, e.to, e.cap);
        FLOW ssum = 0, tsum = 0;
        for (int v = 0; v < N; v++) {
            if (dss[v] > 0) ssum += dss[v], preG.add_edge(s, v, dss[v]);
            else if (dss[v] < 0) tsum -= dss[v], preG.add_edge(v, t, -dss[v]);
        }

        // feasibility check
        if (ssum != tsum) return {false, COST(0)};
        if (Dinic(preG, s, t) < ssum) return {false, COST(0)};

        // come down to min-cost circulation
        for (int i = 0; i < (int)edges.size(); i++) {
            const auto &e = edges[i];
            const auto &ge = preG.get_edge(i);
            G.add_edge(ge.from, ge.to, ge.cap, ge.flow, e.cost);
        }
        COST mincost = MinCostCirculation(G);

        // find dual
        if (calc_potential) {
            G.calc_potential();
            dual = G.pot;
        }
        return {true, mincost};
    }
};

// Network Simplex Method
template<class FLOW, class COST> struct MinCostBFlowByNetworkSimplex {
    // inner Edge
    struct InnerEdge {
        int from, to;
        FLOW cap;
        COST cost;
        InnerEdge(int from_, int to_, FLOW cap_, COST cost_) : from(from_), to(to_), cap(cap_), cost(cost_) {}
    };
    struct Parent {
        int p, e;
        FLOW up, down;
    };

    // inner values
    int N, original_edge_size;
    vector<InnerEdge> edges;
    vector<FLOW> dss;  // demand (< 0) and supply (> 0)
    bool feasible;
    COST total_cost;
    vector<COST> dual;

    // intermediate results
    int BUCKET_SIZE, MINOR_LIMIT;
    vector<Parent> parents;
    vector<int> depth, nex, pre, candidates;

    // constructor
    explicit MinCostBFlowByNetworkSimplex(int n = 0) : N(n), dss(n) {}

    // setter
    void add_edge(int from, int to, FLOW cap, COST cost) {
        assert(cap >= 0);
        edges.emplace_back(from, to, cap, cost);
        edges.emplace_back(to, from, 0, -cost);
    }
    void set_ds(int v, FLOW ds) {
        assert(0 <= v && v < N);
        dss[v] = ds;
    }
    void set_ds(const vector<FLOW> &vds) {
        assert((int)vds.size() == N);
        dss = vds;
    }

    // getter
    FLOW get_flow(int i) const {
        return edges[(i * 2) ^ 1].cap;
    }
    COST get_dual(int v) const {
        return dual[v];
    }
    vector<COST> get_duals() const {
        return dual;
    }

    // solver
    pair<bool, COST> solve() {
        BUCKET_SIZE = max(int(sqrt(double(edges.size())) * 0.2), 10);
        MINOR_LIMIT = max(int(BUCKET_SIZE * 0.1), 3);
        precompute();
        candidates.reserve(BUCKET_SIZE);
        int ei = 0;
        while (true) {
            for (int i = 0; i < MINOR_LIMIT; i++) if (!minor()) break;
            COST best = 0;
            int best_ei = -1;
            candidates.clear();
            for (int i = 0; i < (int)edges.size(); i++) {
                if (edges[ei].cap > 0) {
                    COST clen = edges[ei].cost + dual[edges[ei ^ 1].to] - dual[edges[ei].to];
                    if (clen < 0) {
                        if (clen < best) best = clen, best_ei = ei;
                        candidates.push_back(ei);
                        if ((int)candidates.size() == BUCKET_SIZE) break;
                    }
                }
                ei++;
                if (ei == (int)edges.size()) ei = 0;
            }
            if (candidates.empty()) break;
            push_flow(best_ei);
        }
        if (!postcompute()) return {false, COST(-1)};
        else return {true, total_cost};
    }

    void connect(int a, int b) {
        nex[a] = b, pre[b] = a;
    }

    void precompute() {
        original_edge_size = (int)edges.size();
        dual.assign(N + 1, 0); 
        parents.resize(N), depth.assign(N + 1, 1); 
        nex.assign((N + 1) * 2, 0), pre.assign((N + 1) * 2, 0);
        COST inf_cost = 1;
        for (int i = 0; i < (int)edges.size(); i += 2) {
            inf_cost += (edges[i].cost >= 0 ? edges[i].cost : -edges[i].cost);
        }
        edges.reserve((int)edges.size() + N * 2);
        for (int i = 0; i < N; i++) {
            if (dss[i] >= 0) {
                edges.push_back(InnerEdge(i, N, 0, inf_cost));
                edges.push_back(InnerEdge(N, i, dss[i], -inf_cost));
                dual[i] = -inf_cost;
            } else {
                edges.push_back(InnerEdge(i, N, -dss[i], -inf_cost));
                edges.push_back(InnerEdge(N, i, 0, inf_cost));
                dual[i] = inf_cost;
            }
            int e = (int)edges.size() - 2;
            parents[i] = {N, e, edges[e].cap, edges[e ^ 1].cap};
        }
        depth[N] = 0;
        for (int i = 0; i < N + 1; i++) connect(i * 2, i * 2 + 1);
        for (int i = 0; i < N; i++) connect(i * 2 + 1, nex[N * 2]), connect(N * 2, i * 2);
    }

    bool postcompute() {
        for (int i = 0; i < N; i++) {
            edges[parents[i].e].cap = parents[i].up;
            edges[parents[i].e ^ 1].cap = parents[i].down;
        }
        feasible = true;
        for (int i = 0; i < N; i++) {
            int e = original_edge_size + i * 2;
            if (dss[i] >= 0) {
                if (edges[e ^ 1].cap > 0) feasible = false;
            } else {
                if (edges[e].cap > 0) feasible = false;
            }
        }
        if (!feasible) return false;
        total_cost = 0;
        for (int i = 0; i < (int)edges.size(); i += 2) {
            total_cost += edges[i ^ 1].cap * edges[i].cost;
        }
        dual.pop_back();
        return true;
    }

    void push_flow(int ei0) {
        int u0 = edges[ei0 ^ 1].to, v0 = edges[ei0].to, del_u = v0;
        FLOW f = edges[ei0].cap;
        COST clen = edges[ei0].cost + dual[u0] - dual[v0];
        bool del_u_side = true;
        int lca = get_lca(u0, v0, f, del_u_side, del_u);
        if (f > 0) {
            int u = u0, v = v0;
            while (u != lca) parents[u].up += f, parents[u].down -= f, u = parents[u].p;
            while (v != lca) parents[v].up -= f, parents[v].down += f, v = parents[v].p;
        }
        int u = u0, par = v0;
        auto p_caps = make_pair(edges[ei0].cap - f, edges[ei0 ^ 1].cap + f);
        COST p_diff = -clen;
        if (!del_u_side) {
            swap(u, par); 
            swap(p_caps.first, p_caps.second);
            p_diff *= -1;
        }
        int par_e = ei0 ^ (del_u_side ? 0 : 1);
        while (par != del_u) {
            int d = depth[par], idx = u * 2;
            while (idx != u * 2 + 1) {
                if (idx % 2 == 0) d++, dual[idx / 2] += p_diff, depth[idx / 2] = d;
                else d--;
                idx = nex[idx];
            }
            connect(pre[u * 2], nex[u * 2 + 1]);
            connect(u * 2 + 1, nex[par * 2]);
            connect(par * 2, u * 2);
            swap(parents[u].e, par_e);
            par_e ^= 1;
            swap(parents[u].up, p_caps.first); 
            swap(parents[u].down, p_caps.second);
            swap(p_caps.first, p_caps.second);
            int next_u = parents[u].p; 
            parents[u].p = par;
            par = u;
            u = next_u;
        }
        edges[par_e].cap = p_caps.first;
        edges[par_e ^ 1].cap = p_caps.second;
    }

    bool minor() {
        if (candidates.empty()) return false;
        COST best = 0;
        int best_ei = -1;
        int i = 0;
        while (i < int(candidates.size())) {
            int ei = candidates[i];
            if (edges[ei].cap <= 0) {
                swap(candidates[i], candidates.back());
                candidates.pop_back();
                continue;
            }
            COST clen = edges[ei].cost + dual[edges[ei ^ 1].to] - dual[edges[ei].to];
            if (clen >= 0) {
                swap(candidates[i], candidates.back());
                candidates.pop_back();
                continue;
            }
            if (clen < best) best = clen, best_ei = ei;
            i++;
        }
        if (best_ei == -1) return false;
        push_flow(best_ei);
        return true;
    }

    int get_lca(int u, int v, FLOW &flow, bool &del_u_side, int &del_u) {
        auto up_u = [&]() {
            if (parents[u].down < flow) flow = parents[u].down, del_u = u, del_u_side = true;
            u = parents[u].p;
        };
        auto up_v = [&]() {
            if (parents[v].up <= flow) flow = parents[v].up, del_u = v, del_u_side = false;
            v = parents[v].p;
        };
        if (depth[u] >= depth[v]) {
            int num = depth[u] - depth[v];
            for (int i = 0; i < num; i++) up_u();
        } else {
            int num = depth[v] - depth[u];
            for (int i = 0; i < num; i++) up_v();
        }
        while (u != v) up_u(), up_v();
        return u;
    }
};

// b-flow manager
template<class FLOW, class COST> struct MinCostBFlow {
    // Edge
    struct InnerEdge {
        int from, to;
        FLOW lower_cap, upper_cap, flow;
        COST cost;
        InnerEdge(int from_, int to_, FLOW lower_, FLOW upper_, COST cost_)
            : from(from_), to(to_), lower_cap(lower_), upper_cap(upper_), flow(0), cost(cost_) {}
        friend ostream& operator << (ostream& s, const InnerEdge& e) {
            return s << e.from << "->" << e.to 
            << " (" << e.flow << "/" << e.lower_cap << "~" << e.upper_cap << ", " << e.cost << ")";
        }
    };

    // inner values
    int N;
    vector<InnerEdge> edges;
    vector<FLOW> lower_dss, upper_dss, dss;  // demand (< 0) and supply (> 0)
    vector<COST> dual;
    
    // constructor
    explicit MinCostBFlow(int n = 0) : N(n), lower_dss(n, 0), upper_dss(n, 0), dss(n, 0) {}

    // setter
    void add_edge(int from, int to, FLOW cap, COST cost) {
        assert(cap >= 0);
        edges.push_back(InnerEdge(from, to, 0, cap, cost));
    }
    void add_edge(int from, int to, FLOW lower_cap, FLOW upper_cap, COST cost) {
        assert(lower_cap <= upper_cap);
        edges.push_back(InnerEdge(from, to, lower_cap, upper_cap, cost));
    }
    void set_ds(int v, FLOW ds) {
        assert(0 <= v && v < N);
        lower_dss[v] = ds, upper_dss[v] = ds;
    }
    void set_ds(int v, FLOW lower_ds, FLOW upper_ds) {
        assert(0 <= v && v < N);
        assert(lower_ds <= upper_ds);
        lower_dss[v] = lower_ds, upper_dss[v] = upper_ds;
    }

    // getter
    InnerEdge &get_edge(int i) {
        return edges[i];
    }
    const InnerEdge &get_edge(int i) const {
        return edges[i];
    }
    vector<InnerEdge> get_edges() const {
        return edges;
    }
    COST get_dual(int v) const {
        return dual[v];
    }
    vector<COST> get_duals() const {
        return dual;
    }

    // solver
    bool pre_compute() {
        bool need_super_node = false;
        for (int v = 0; v < N; v++) {
            if (lower_dss[v] == upper_dss[v]) dss[v] = lower_dss[v];
            else need_super_node = true;
        }

        // lower_ds, upper_ds -> strict ds
        if (need_super_node) {
            int super = N;
            dss.assign(N + 1, 0);
            for (int v = 0; v < N; v++) {
                if (lower_dss[v] >= 0) {
                    add_edge(super, v, lower_dss[v], upper_dss[v], 0);
                } else if (upper_dss[v] < 0) {
                    add_edge(v, super, -upper_dss[v], -lower_dss[v], 0);
                } else {
                    add_edge(super, v, upper_dss[v], 0);
                    add_edge(v, super, -lower_dss[v], 0);
                }
            }
        }

        // push lower_cap
        for (const auto &e : edges) {
            dss[e.to] += e.lower_cap, dss[e.from] -= e.lower_cap;
        }
        return need_super_node;
    }
    pair<bool, COST> solve(const string solver = "network_simplex", bool calc_potential = false) {
        bool need_super_node = pre_compute();
        COST res = 0;
        if (solver == "primal_dual") {
            MinCostBFlowByPrimalDual<FLOW, COST> G(N + (int)need_super_node);
            G.set_ds(dss);
            for (const auto &e : edges) G.add_edge(e.from, e.to, e.upper_cap - e.lower_cap, e.cost);
            auto [feasible, mincost] = G.solve(calc_potential);
            if (!feasible) return {false, COST(0)};
            for (int i = 0; i < (int)edges.size(); i++) {
                auto &e = edges[i];
                const auto &ge = G.get_edge(i);
                e.flow = e.upper_cap - ge.cap;
                res += e.flow * e.cost;
            }
            if (calc_potential) {
                dual = G.get_duals();
                if (need_super_node) dual.pop_back();
            }
        } else if (solver == "cost_scaling") {
            MinCostBFlowByCostScaling<FLOW, COST> G(N + (int)need_super_node);
            G.set_ds(dss);
            for (const auto &e : edges) G.add_edge(e.from, e.to, e.upper_cap - e.lower_cap, e.cost);
            auto [feasible, mincost] = G.solve(calc_potential);
            if (!feasible) return {false, COST(0)};
            for (int i = 0; i < (int)edges.size(); i++) {
                auto &e = edges[i];
                const auto &ge = G.get_edge(i);
                e.flow = e.upper_cap - ge.cap;
                res += e.flow * e.cost;
            }
            if (calc_potential) {
                dual = G.get_duals();
                if (need_super_node) dual.pop_back();
            }
        } else if (solver == "network_simplex") {
            MinCostBFlowByNetworkSimplex<FLOW, COST> G(N + (int)need_super_node);
            G.set_ds(dss);
            for (const auto &e : edges) G.add_edge(e.from, e.to, e.upper_cap - e.lower_cap, e.cost);
            auto [feasible, mincost] = G.solve();
            if (!feasible) return {false, COST(0)};
            for (int i = 0; i < (int)edges.size(); i++) {
                auto &e = edges[i];
                e.flow = e.lower_cap + G.get_flow(i);
                res += e.flow * e.cost;
            }
            if (calc_potential) {
                dual = G.get_duals();
                if (need_super_node) dual.pop_back();
            }
        }
        return {true, res};
    }
};


// Push-Relabel
// we can skip 2nd phase if we should know only about maxflow and residual graph
template<class FLOW> FLOW PushRelabel
(FlowGraph<FLOW> &G, int s, int t, FLOW limit_flow, bool do_2nd_phase = false) {
    assert(0 <= s && s < (int)G.size());
    assert(0 <= t && t < (int)G.size());
    assert(s != t);
    const int GlobalRelabelRreq = 5;
    const bool UseGapRelabeling = true;
    struct PushQueue {
        vector<pair<int, int>> even, odd;
        int num_even, num_odd;
        void init(int N) { even.resize(N), odd.resize(N), num_even = num_odd = 0; }
        void clear() { num_even = num_odd = 0; }
        int size() const { return num_even + num_odd; }
        bool empty() const { return size() == 0; }
        int highest() const {
            int a = (num_even > 0 ? even[num_even - 1].second : -1);
            int b = (num_odd > 0 ? odd[num_odd - 1].second : -1);
            return (a > b ? a : b);
        }
        void push(int v, int h) {
            if (h & 1) odd[num_odd++] = {v, h};
            else even[num_even++] = {v, h};
        }
        int pop() {
            if (num_even == 0 || (num_odd > 0 && odd[num_odd - 1].second > even[num_even - 1].second)) {
                return odd[--num_odd].first;
            } else {
                return even[--num_even].first;
            }
        }
    } push_que;

    int gap, N = (int)G.size();
    vector<int> dist, dcnt;
    vector<FLOW> excess;

    // heuristics
    auto global_relabeling = [&](int t) -> void {
        push_que.clear();
        if (UseGapRelabeling) gap = 1, dcnt.assign(N + 1, 0);
        dist.assign(N, N);
        dist[t] = 0;
        static vector<int> que;
        if (que.empty()) que.resize(N);
        que[0] = t;
        int qb = 0, qe = 1;
        while (qb < qe) {
            int now = que[qb++];
            if (UseGapRelabeling) gap = dist[now] + 1, dcnt[dist[now]]++;
            if (excess[now] > 0) push_que.push(now, dist[now]);
            for (const auto &e : G[now]) {
                if (G.get_rev_edge(e).cap > 0 && dist[e.to] == N) {
                    dist[e.to] = dist[now] + 1;
                    while ((int)que.size() <= qe) que.emplace_back(0);
                    que[qe++] = e.to;
                }
            }
        }
    };

    // push
    auto push = [&](int v, FlowEdge<FLOW> &e) -> void {
        auto &re = G.get_rev_edge(e);
        FLOW delta = e.cap < excess[v] ? e.cap : excess[v];
        excess[v] -= delta, e.cap -= delta, e.flow += delta;
        excess[e.to] += delta, re.cap += delta, re.flow -= delta;
        if (excess[e.to] > 0 && excess[e.to] <= delta) {
            if (!UseGapRelabeling || dist[e.to] <= gap) push_que.push(e.to, dist[e.to]);
        }
    };

    // run
    auto run = [&](int t) -> void {
        global_relabeling(t);
        int tick = (int)G.pos.size() * GlobalRelabelRreq;
        while (!push_que.empty()) {
            int v = push_que.pop();
            if (UseGapRelabeling && dist[v] > gap) continue;
            int dnex = N * 2 - 1;
            for (auto &e : G[v]) {
                if (e.cap <= 0) continue;
                if (dist[e.to] == dist[v] - 1) {
                    push(v, e);
                    if (excess[v] <= 0) break;
                } else {
                    if (dist[e.to] + 1 < dnex) dnex = dist[e.to] + 1;
                }
            }
            if (excess[v] > 0) {
                if (UseGapRelabeling) {
                    if (dnex != dist[v] && dcnt[dist[v]] == 1 && dist[v] < gap) gap = dist[v];
                    if (dnex == gap) gap++;
                    while (push_que.highest() > gap) push_que.pop();
                    if (dnex > gap) dnex = N;
                    if (dist[v] != dnex) dcnt[dist[v]]--, dcnt[dnex]++;
                }
                dist[v] = dnex;
                if (!UseGapRelabeling || dist[v] < gap) push_que.push(v, dist[v]);
            }
            if (GlobalRelabelRreq && --tick == 0) {
                tick = (int)G.pos.size() * GlobalRelabelRreq;
                global_relabeling(t);
            }
        }
    };

    // 1st phase: find preflow
    excess.assign(N, 0), dist.assign(N, 0);
    excess[s] += limit_flow, excess[t] -= limit_flow;
    dist[s] = N;
    if (UseGapRelabeling) gap = 1, dcnt.assign(N + 1, 0), dcnt[0] = N - 1;
    push_que.init(N);
    for (auto &e : G[s]) push(s, e);
    run(t);
    FLOW res = excess[t] + limit_flow;

    // 2nd phase: convert preflow into flow
    if (do_2nd_phase) {
        excess[s] += excess[t], excess[t] = 0;
        global_relabeling(s);
        run(s);
        assert(excess == vector<FLOW>(N, 0));
    }
    return res;
}

template<class FLOW> FLOW PushRelabel
(FlowGraph<FLOW> &G, int s, int t, bool do_2nd_phase = false) {
    return PushRelabel(G, s, t, numeric_limits<FLOW>::max(), do_2nd_phase);
}


//------------------------------//
// Examples
//------------------------------//

int main() {
    int N, M, K;
    long long INF = 1LL << 40;
    cin >> N >> M >> K;
    
    vector<long long> A(N), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i], B[i]--;

    for (int D = 1; D <= M; D++) {
        int s = (D * 2 + 1) * N, t = s + 1;
        FlowGraph<long long> G(t + 1);
        for (int i = 0; i < N; i++) {
            G.add_edge(s, i, A[i]);
            if (i != B[D-1]) G.add_edge(i + D * 2 * N, t, INF);
        }
        for (int d = 0; d < D; d++) {
            for (int i = 0; i < N; i++) {
                G.add_edge(i + d * 2 * N, i + (d * 2 + 1) * N, K);
                G.add_edge(i + d * 2 * N, i + (d * 2 + 2) * N, INF);
                for (int di = -1; di <= 1; di += 2) {
                    int i2 = (i + di + N) % N;
                    G.add_edge(i + (d * 2 + 1) * N, i2 + (d * 2 + 2) * N, INF);
                }
            }
        }
        long long maxflow = PushRelabel(G, s, t);
        cout << maxflow << endl;
    }
}