#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

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

class PushRelabel {
public:
    int numOfNode;
    vector<Node> nodeList;
    vector<vector<Edge>> graph;
    queue<int> active_nodes;
    int epsilon = 1;
    int SCALING_FACTOR = 2;
    int COST_SCALING_FACTOR = 1;

    PushRelabel(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 addEdge(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 = max(epsilon, abs(cost) * COST_SCALING_FACTOR);
    }

    // sourceからsinkへの最大流を求める
    int minimumCostFlow(int source, int sink, int flow) {

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

        while (epsilon > 1.0) {
//            cout << "epsilon:" << epsilon << "--------------------------------------------------" << endl;
//            show();
//            cout << "ex ";
//            for (int u = 0; u < nodeList.size(); ++u) {
//                cout << u << ":" << nodeList[u].excessFlow << ", ";
//            }
//            cout << endl;
//            cout << "pot ";
//            for (int u = 0; u < nodeList.size(); ++u) {
//                cout << u << ":" << nodeList[u].potential << ", ";
//            }
//            cout << endl;

            for (int u = 0; u < numOfNode; ++u) {
                for (int v = 0; v < graph.at(u).size(); ++v) {
                    const Edge &edge = graph.at(u).at(v);
                    if (edge.is_rev) {
                        continue;
                    }
                    const double reduced_cost = calc_reduced_cost(edge);
//                    cout << u << " -> " << edge.to << ":" << reduced_cost << endl;
                    if (reduced_cost < 0) {
                        if (edge.capacity - edge.flow > 0) {
                            int f = edge.capacity - edge.flow;
                            graph.at(u).at(v).flow = edge.capacity;
                            graph.at(edge.to).at(edge.rev).flow = 0;
                            nodeList.at(u).excessFlow -= f;
                            nodeList.at(edge.to).excessFlow += f;
//                            cout << "push "<< edge.capacity << " " << edge.from << "->" << edge.to << endl;
                        }
                    }
                    if (reduced_cost > 0) {
                        if (edge.flow > 0) {
                            int f = graph.at(u).at(v).flow;
                            graph.at(u).at(v).flow = 0;
                            graph.at(edge.to).at(edge.rev).flow = edge.capacity;
                            nodeList.at(u).excessFlow += f;
                            nodeList.at(edge.to).excessFlow -= f;
//                            cout << "modosu " << f << " " << edge.from << "->" << edge.to << endl;
                        }
                    }
                }
            }

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

            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)) {
//                        cout << "relabel node " << node << "(p:" << nodeList.at(node).potential << " -> ";
                        relabel(node);
//                        cout << nodeList.at(node).potential << ")" << endl;
                        active_nodes.push(node);
                        break;
                    }
                }
            }

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

//        cout << "RESULT" << endl;
//        for (int u = 0; u < nodeList.size(); ++u) {
//            cout << "node:" << u << "(ex:" << nodeList.at(u).excessFlow << ", potential:" << nodeList.at(u).potential
//                 << ")" << endl;
//        }
        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;
//                cout << "flow:" << edge.flow << "(" << edge.from << " -> " << edge.to << ")" << endl;
            }
        }

        return total_cost;
    }

private:

    void show() {
        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;
                }
                cout << "flow:" << edge.flow << "(" << edge.from << " -> " << edge.to << ")" << endl;
            }
        }

    }

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

    // オーバーフロー頂点を探す
    void get_active_nodes() {
//        cout << "ex ";
        for (int u = 0; u < nodeList.size(); ++u) {
//            cout << u << ":" << nodeList[u].excessFlow << ", ";
            if (nodeList[u].excessFlow > 0) {
                active_nodes.push(u);
            }
        }
//        cout << endl;
    }

    // fromノードから他のノードにpushする
    bool push(int from) {
        if (nodeList.at(from).excessFlow == 0) {
//            cout << "can't push not excess" << endl;
            return false;
        }
        assert(nodeList.at(from).excessFlow > 0);

        for (int i = graph.at(from).size() - 1; i >= 0; --i) {
//        for (Edge &edge : graph.at(from)) {
            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 (is_admissible(edge)) {
            if (reduced_cost < 0) {
                int flow = min(edge.capacity - edge.flow, nodeList[from].excessFlow);
//                cout << "push " << from << " to " << to << " " << flow << " unit" << endl;
                edge.flow += flow;
                graph.at(edge.to).at(edge.rev).flow -= flow;
                nodeList.at(from).excessFlow -= flow;
                nodeList.at(edge.to).excessFlow += flow;
                if (nodeList.at(edge.to).excessFlow > 0 and nodeList.at(edge.to).excessFlow <= flow) {
                    active_nodes.push(edge.to);
                }
                return true;
            }
        }
//        cout << "can't push" << endl;
        return false;
    }

    // fromのpotentialを修正
    void relabel(int from) {
        double min_potential = INT_MAX;
        for (const Edge &edge : graph.at(from)) {
            if (edge.capacity - edge.flow > 0) {
                min_potential = 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() {
    cin.tie(0);
    ios::sync_with_stdio(false);


    int V, E, F;
    cin >> V >> E >> F;
    Dinic dn(V);
    PushRelabel pd(V);
    for (int i = 0; i < E; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.addEdge(u, v, c, d);
        dn.add_edge(u, v, c);
    }

    if (dn.max_flow(0, V - 1) < F) {
        cout << -1 << endl;
    }
    else {
        cout << pd.minimumCostFlow(0, V - 1, F) << endl;
    }
    return 0;

}


Measured memory_bytes: 3376