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

class CostScalingPushRelabel
{
public:
    struct Edge
    {
        const int from;
        const int to;       // 行き先のノード番号
        const int rev;      // 逆辺のindex. graph[to][rev]でアクセスできる
        int flow;           // 流量
        const int capacity; // 容量
        const int cost;     // cost
        const bool is_rev;  // 逆辺かどうか
        Edge(int from, int to, int rev, int flow, int capacity, int cost, bool is_rev) : from(from), to(to), rev(rev), flow(flow), capacity(capacity), cost(cost), is_rev(is_rev) {}
    };

    struct Node
    {
        int height = 0;
        int excessFlow = 0;   // 残存量
        double potential = 0; // ポテンシャル
        Node(int height, int excessFlow, int potential) : height(height), excessFlow(excessFlow), potential(potential) {}
    };

    int numOfNode;
    std::vector<Node> nodeList;
    std::vector<std::vector<Edge>> graph;
    std::queue<int> active_nodes;
    int epsilon = 1;
    int SCALING_FACTOR = 2;
    int COST_SCALING_FACTOR = 1;

    CostScalingPushRelabel(unsigned int numOfNode) : numOfNode(numOfNode), COST_SCALING_FACTOR(2 * numOfNode)
    {
        for (int i = 0; i < numOfNode; ++i)
        {
            nodeList.emplace_back(Node(0, 0, 0));
        }
        graph.resize(numOfNode);
    }

    void add_edge(int from, int to, int capacity, int cost)
    {
        graph[from].emplace_back(Edge(from, to, (int)graph[to].size(), 0, capacity, cost, false));
        graph[to].emplace_back(Edge(to, from, (int)graph[from].size() - 1, capacity, capacity, -cost, true));
        epsilon = std::max(epsilon, abs(cost) * COST_SCALING_FACTOR);
    }

    // sourceからsinkへの最大流を求める
    // flowを流せること前提
    int minimum_cost_flow(const int source, const int sink, const int flow)
    {

        nodeList.at(source).excessFlow = flow;
        nodeList.at(sink).excessFlow = -flow;

        while (epsilon > 1.0)
        {
            for (int u = 0; u < numOfNode; ++u)
            {
                for (int v = 0; v < graph.at(u).size(); ++v)
                {
                    Edge &edge = graph.at(u).at(v);
                    if (edge.is_rev)
                    {
                        continue;
                    }
                    const double reduced_cost = calc_reduced_cost(edge);
                    if (reduced_cost < 0)
                    {
                        if (edge.capacity - edge.flow > 0)
                        {
                            int f = edge.capacity - edge.flow;
                            push_flow(edge, f);
                        }
                    }
                    if (reduced_cost > 0)
                    {
                        if (edge.flow > 0)
                        {
                            int f = -graph.at(u).at(v).flow;
                            push_flow(edge, f);
                        }
                    }
                }
            }

            get_active_nodes();
            while (not active_nodes.empty())
            {
                int node = active_nodes.front();
                active_nodes.pop();

                while (nodeList.at(node).excessFlow > 0)
                {
                    if (not push(node))
                    {
                        relabel(node);
                        active_nodes.push(node);
                        break;
                    }
                }
            }

            epsilon = std::max(1, epsilon / SCALING_FACTOR);
        }

        double total_cost = 0;
        for (int u = 0; u < numOfNode; ++u)
        {
            for (int v = 0; v < graph.at(u).size(); ++v)
            {
                Edge &edge = graph.at(u).at(v);
                if (edge.is_rev)
                {
                    continue;
                }
                total_cost += edge.flow * edge.cost;
            }
        }

        return total_cost;
    }

private:
    void print()
    {
        for (int u = 0; u < graph.size(); ++u)
        {
            for (int v = 0; v < graph.at(u).size(); ++v)
            {
                const Edge &edge = graph.at(u).at(v);
                if (edge.is_rev)
                {
                    continue;
                }
                std::cout << edge.from << " -> " << edge.to << "(" << edge.flow << ")" << std::endl;
            }
        }

        std::cout << "excess: ";
        for (int u = 0; u < nodeList.size(); ++u)
        {
            std::cout << u << ":" << nodeList[u].excessFlow << ", ";
        }
        std::cout << std::endl;
        std::cout << "potential: ";
        for (int u = 0; u < nodeList.size(); ++u)
        {
            std::cout << u << ":" << nodeList[u].potential << ", ";
        }
        std::cout << std::endl;
    }

    void push_flow(Edge &edge, int flow)
    {
        edge.flow += flow;
        graph.at(edge.to).at(edge.rev).flow -= flow;
        nodeList.at(edge.from).excessFlow -= flow;
        nodeList.at(edge.to).excessFlow += flow;
    }

    double calc_reduced_cost(const Edge &edge)
    {
        return edge.cost * COST_SCALING_FACTOR - nodeList.at(edge.from).potential + nodeList.at(edge.to).potential;
    }

    // activeな頂点を取得
    void get_active_nodes()
    {
        for (int u = 0; u < nodeList.size(); ++u)
        {
            if (nodeList[u].excessFlow > 0)
            {
                active_nodes.push(u);
            }
        }
    }

    // fromノードから他のノードにpushする
    bool push(const int from)
    {
        if (nodeList.at(from).excessFlow == 0)
        {
            return false;
        }
        assert(nodeList.at(from).excessFlow > 0);

        for (int i = graph.at(from).size() - 1; i >= 0; --i)
        {
            Edge &edge = graph.at(from).at(i);
            const int to = edge.to;
            if (edge.flow == edge.capacity)
            {
                continue;
            }
            const double reduced_cost = calc_reduced_cost(edge);

            if (reduced_cost < 0)
            {
                int flow = std::min(edge.capacity - edge.flow, nodeList[from].excessFlow);
                push_flow(edge, flow);

                if (nodeList.at(edge.to).excessFlow > 0 and nodeList.at(edge.to).excessFlow <= flow)
                {
                    active_nodes.push(edge.to);
                }
                return true;
            }
        }
        return false;
    }

    // fromのpotentialを修正
    void relabel(const int from)
    {
        double min_potential = INT_MAX;
        for (const Edge &edge : graph.at(from))
        {
            if (edge.capacity - edge.flow > 0)
            {
                min_potential = std::min(min_potential, edge.cost * COST_SCALING_FACTOR + nodeList[edge.to].potential + epsilon);
            }
        }
        assert(min_potential != INT_MAX);
        nodeList[from].potential = min_potential;
    }
};

class Dinic
{

public:
    struct Edge
    {
        const int to;        // 行き先のノードid
        long long flow;      // 流量
        const long long cap; // 容量
        const int rev;       // 逆辺のノードid
        const bool is_rev;   // 逆辺かどうか
        Edge(int to, long long flow, long long cap, int rev, bool is_rev) : to(to), flow(flow), cap(cap), rev(rev), is_rev(is_rev)
        {
            assert(this->cap >= 0);
        }
    };

    vector<vector<Edge>> graph; // グラフの隣接リスト表現
    vector<int> level;          // sからの距離
    vector<unsigned int> iter;  // どこまで調べ終わったか

    explicit Dinic(unsigned int num_of_node)
    {
        assert(num_of_node > 0);
        graph.resize(num_of_node);
        level.resize(num_of_node);
        iter.resize(num_of_node);
    }

    // fromからtoへ向かう容量capの辺をグラフに追加する
    void add_edge(unsigned int from, unsigned int to, long long cap)
    {
        graph[from].emplace_back(Edge(to, 0, cap, (unsigned int)graph[to].size(), false));
        graph[to].emplace_back(Edge(from, cap, cap, (unsigned int)graph[from].size() - 1, true));
    }

    // sからtへの最大流を求める
    long long max_flow(unsigned int s, unsigned int t)
    {
        long long flow = 0;
        while (true)
        {
            bfs(s);
            if (level.at(t) < 0)
            {
                return flow;
            }
            fill(iter.begin(), iter.end(), 0);
            long long f;
            while ((f = dfs(s, t, INT_MAX)) > 0)
            {
                flow += f;
            }
        }
    }

private:
    // sからの最短距離をBFSで計算する
    void bfs(unsigned int s)
    {
        fill(level.begin(), level.end(), -1);
        queue<unsigned int> que;
        level.at(s) = 0;
        que.push(s);
        while (not que.empty())
        {
            unsigned int v = que.front();
            que.pop();
            for (int i = 0; i < graph.at(v).size(); ++i)
            {
                Edge &e = graph.at(v).at(i);
                if ((e.cap - e.flow) > 0 and level.at(e.to) < 0)
                {
                    level.at(e.to) = level.at(v) + 1;
                    que.push(e.to);
                }
            }
        }
    }

    // 増加パスをDFSで探す
    long long dfs(unsigned int v, unsigned int t, long long f)
    {
        if (v == t)
        {
            return f;
        }
        for (unsigned int &i = iter.at(v); i < graph.at(v).size(); ++i)
        {
            Edge &e = graph.at(v).at(i);
            if ((e.cap - e.flow) > 0 and level.at(v) < level.at(e.to))
            {
                long long d = dfs(e.to, t, min(f, e.cap - e.flow));
                if (d > 0)
                {
                    e.flow += d;
                    graph.at(e.to).at(e.rev).flow -= d;
                    return d;
                }
            }
        }
        return 0;
    }
};

int main()
{
    int V, E, F;
    cin >> V >> E >> F;
    Dinic dinic(V);
    CostScalingPushRelabel min_cost(V);
    for (size_t i = 0; i < E; i++)
    {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        dinic.add_edge(u, v, c);
        min_cost.add_edge(u, v, c, d);
    }

    auto flow = dinic.max_flow(0, V - 1);
    if (flow < F)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << min_cost.minimum_cost_flow(0, V - 1, F) << endl;
    }
}


Measured memory_bytes: 3308