#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

template <class T>
using lp_queue=priority_queue<T, deque<T>, greater<T>>;

template <class Weight>
struct Arc {
    size_t src, dst;
    Weight capacity, cost;
    size_t rev;
    Arc() {}
    Arc(size_t src, size_t dst, Weight capacity, Weight cost):
        src(src), dst(dst), capacity(capacity), cost(cost), rev(-1)
    {}
};

template <class Weight>
bool operator<(const Arc<Weight> &e, const Arc<Weight> &f) {
    if (e.capacity != f.capacity) {
        return e.capacity > f.capacity;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

template <class Weight>
using Arcs=vector<Arc<Weight>>;
template <class Weight>
using Node=vector<Arc<Weight>>;

template <class Weight>
struct FlowNetwork: public vector<Node<Weight>> {
    FlowNetwork() {}
    FlowNetwork(size_t V): vector<Node<Weight>>(V) {}
    void join(size_t s, size_t d, Weight c=1, Weight k=1) {
        (*this)[s].push_back(Arc<Weight>(s, d, c, k));
        (*this)[d].push_back(Arc<Weight>(d, s, c, k));

        (*this)[s].back().rev = (*this)[d].size()-1;
        (*this)[d].back().rev = (*this)[s].size()-1;
    }
    void connect(size_t s, size_t d, Weight c=1, Weight k=1) {
        (*this)[s].push_back(Arc<Weight>(s, d, c, k));
        (*this)[d].push_back(Arc<Weight>(d, s, 0, -k));

        (*this)[s].back().rev = (*this)[d].size()-1;
        (*this)[d].back().rev = (*this)[s].size()-1;
    }
    Arc<Weight> &reverse(const Arc<Weight> &e) {
        // Assert: e in (*this)
        return (*this)[e.dst][e.rev];
    }
};

template <class Weight>
pair<Weight, Weight> mincost_flow(
    FlowNetwork<Weight> &g, size_t s, size_t t, Weight F=INF
) {
    // maximum flow (at most F) and its cost
    size_t V=g.size();
    vector<Weight> pot(V);

    Weight maxflow=0, mincost=0;
    while (F > maxflow) {
        vector<Weight> d(V, INF); d[s]=0;
        vector<Arc<Weight> *> prev(V, NULL);
        lp_queue<pair<Weight, size_t>> q; q.push(make_pair(0, s));
        while (!q.empty()) {
            pair<Weight, size_t> p=q.top(); q.pop();
            size_t v=p.second;
            if (d[v] < p.first) continue;

            for (Arc<Weight> &e: g[v]) {
                if (e.capacity <= 0) continue;

                if (d[e.dst] > d[e.src] + e.cost + pot[e.src] - pot[e.dst]) {
                    d[e.dst] = d[e.src] + e.cost + pot[e.src] - pot[e.dst];
                    prev[e.dst] = &e;
                    q.push(make_pair(d[e.dst], e.dst));
                }
            }
        }

        if (d[t] == INF) break;

        for (size_t v=0; v<V; ++v)
            pot[v] += d[v];

        Weight f=F-maxflow;
        for (Arc<Weight> *e=prev[t]; e!=NULL; e=prev[e->src])
            f = min(f, e->capacity);

        maxflow += f;
        mincost += f * pot[t];
        for (Arc<Weight> *e=prev[t]; e!=NULL; e=prev[e->src]) {
            e->capacity -= f;
            g.reverse(*e).capacity += f;
        }
    }

    return make_pair(maxflow, mincost);
}

int main() {
    size_t V, E;
    Weight F;
    scanf("%zu %zu %lld", &V, &E, &F);

    FlowNetwork<Weight> g(V);
    for (size_t i=0; i<E; ++i) {
        size_t u, v;
        Weight c, d;
        scanf("%zu %zu %lld %lld", &u, &v, &c, &d);

        g.connect(u, v, c, d);
    }

    pair<Weight, Weight> mcflow=mincost_flow(g, 0, V-1, F);
    if (mcflow.first < F) {
        printf("-1\n");
    } else {
        printf("%lld\n", mcflow.second);
    }

    return 0;
}

Measured memory_bytes: 2904