#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 };


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

    std::vector<std::vector<Edge>> graph; // グラフの隣接リスト表現
    std::vector<int> level;          // sからの距離
    std::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);
        std::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, std::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;
    }
};


using namespace std;

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


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

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

}


Measured memory_bytes: 3348