#include <bits/stdc++.h>
#define show(x) cout << #x << " = " << x << endl

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz=" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = 1e9 + 7;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

class CostFlow
{
public:
    using T = ll;
    struct Edge {
        Edge(const int from_, const int to_, const int reverse_, const T capacity_, const T cost_) : from{from_}, to{to_}, reverse{reverse_}, capacity{capacity_}, flow{0}, cost{cost_} {}
        int from;
        int to;
        int reverse;
        T capacity;
        T flow;
        T cost;
    };

    CostFlow(const int v) : m_v{v}
    {
        m_table.resize(v);
        m_dist.resize(v);
        m_potential.resize(v);
        m_prev_v.resize(v);
        m_prev_e.resize(v);
    }

    void addEdge(const int from, const int to, const T capacity, const T cost)
    {
        m_table[from].push_back(Edge{from, to, (int)m_table[to].size(), capacity, cost});
        m_table[to].push_back(Edge{to, from, (int)m_table[from].size() - 1, 0, -cost});
    }

    T minCostFlow(const int s, const int t, int f)
    {
        using P = pair<T, int>;
        T res = 0;
        fill(m_potential.begin(), m_potential.end(), 0);

        // // Bellman-Ford(Replace this when DAG)
        // for (int i = 0; i < m_v; i++) {
        //     m_potential[i] = INF<T>;
        // }
        // m_potential[s] = 0;
        // bool no_negative_loop = true;
        // for (int i = 0; i < m_v; i++) {
        //     for (int v = 0; v < m_v; v++) {
        //         if (m_potential[v] != INF<T>) {
        //             for (const auto& e : m_table[v]) {
        //                 if (e.capacity <= 0) {
        //                     continue;
        //                 }
        //                 if (m_potential[e.to] > m_potential[v] + e.cost) {
        //                     m_potential[e.to] = m_potential[v] + e.cost;
        //                     if (i == m_v - 1) {
        //                         m_potential[e.to] = -INF<T>;  // Confirm " -INF < min(possible_cost) * V "
        //                         no_negative_loop = false;
        //                     }
        //                 }
        //             }
        //         }
        //     }
        // }
        // if (not no_negative_loop) {
        //     // ????????¨?????????
        // }
        ////show(m_potential)

        while (f > 0) {
            // Dijkstra
            priority_queue<P, vector<P>, greater<P>> q;
            fill(m_dist.begin(), m_dist.end(), INF<T>);
            m_dist[s] = 0;
            q.push(make_pair(0, s));
            while (not q.empty()) {
                const P p = q.top();
                q.pop();
                const int v = p.second;
                if (m_dist[v] < p.first) {
                    continue;
                }
                for (int i = 0; i < m_table[v].size(); i++) {
                    const auto& e = m_table[v][i];
                    if (e.capacity > e.flow and m_dist[e.to] > m_dist[v] + e.cost + m_potential[v] - m_potential[e.to]) {
                        m_dist[e.to] = m_dist[v] + e.cost + m_potential[v] - m_potential[e.to];
                        m_prev_v[e.to] = v;
                        m_prev_e[e.to] = i;
                        q.push(make_pair(m_dist[e.to], e.to));
                    }
                }
            }
            if (m_dist[t] == INF<T>) {
                return -1;
            }
            for (int v = 0; v < m_v; v++) {
                m_potential[v] += m_dist[v];
            }

            T d = f;
            for (int v = t; v != s; v = m_prev_v[v]) {
                const auto& e = m_table[m_prev_v[v]][m_prev_e[v]];
                d = min(d, e.capacity - e.flow);
            }
            f -= d;
            res += d * m_potential[t];
            for (int v = t; v != s; v = m_prev_v[v]) {
                auto& e = m_table[m_prev_v[v]][m_prev_e[v]];
                e.flow += d;
                m_table[v][e.reverse].flow -= d;
            }
        }
        return res;
    }

private:
    const int m_v;
    vector<vector<Edge>> m_table;
    vector<T> m_dist;
    vector<T> m_potential;
    vector<int> m_prev_v;
    vector<int> m_prev_e;
};
int main()
{
    int V, E;
    ll F;
    std::cin >> V >> E >> F;
    CostFlow f(V);
    for (ll i = 0; i < E; i++) {
        int u, v;
        ll c, d;
        cin >> u >> v >> c >> d;
        f.addEdge(u, v, c, d);
    }
    cout << f.minCostFlow(0, V - 1, F) << endl;
    return 0;
}

Measured memory_bytes: 3200