#include <stdexcept>
#include <cmath>
#include <utility>
#include <queue>
#include <limits>
#include <iostream>
#include <vector>
#include <cstddef>
#include <type_traits>
namespace loquat {
using vertex_t = size_t;
}
namespace loquat {
namespace edge_param {
struct to_ {
	vertex_t to;
	explicit to_(vertex_t t = 0)
		: to(t)
	{ }
};
template <typename T>
struct weight_ {
	using weight_type = T;
	weight_type weight;
	explicit weight_(const weight_type& w = weight_type())
		: weight(w)
	{ }
};
template <typename T>
using weight = weight_<T>;
template <typename T>
struct capacity_ {
	using capacity_type = T;
	capacity_type capacity;
	explicit capacity_(const capacity_type& c = capacity_type())
		: capacity(c)
	{ }
};
template <typename T>
using capacity = capacity_<T>;
}
namespace detail {
template <typename T, typename... Params>
struct edge_param_wrapper : public T, edge_param_wrapper<Params...> {
	template <typename U, typename... Args>
	explicit edge_param_wrapper(U&& x, Args&&... args)
		: T(std::forward<U>(x))
		, edge_param_wrapper<Params...>(std::forward<Args>(args)...)
	{ }
};
template <typename T>
struct edge_param_wrapper<T> : public T {
	template <typename U>
	explicit edge_param_wrapper(U&& x)
		: T(std::forward<U>(x))
	{ }
};
}
template <typename... Params>
struct edge : public detail::edge_param_wrapper<edge_param::to_, Params...> {
	edge()
		: detail::edge_param_wrapper<edge_param::to_, Params...>()
	{ }
	template <typename... Args>
	explicit edge(Args&&... args)
		: detail::edge_param_wrapper<edge_param::to_, Params...>(
			std::forward<Args>(args)...)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
struct has_weight {
private:
	template <typename U>
	static std::true_type check_type(typename U::weight_type *);
	template <typename U>
	static std::false_type check_type(...);
	template <typename U>
	static auto check_member(const U& x)
		-> decltype(x.weight, std::true_type());
	static std::false_type check_member(...);
public:
	static const bool value =
		decltype(check_type<EdgeType>(nullptr))::value &&
		decltype(check_member(std::declval<EdgeType>()))::value;
};
template <typename EdgeType>
struct has_capacity {
private:
	template <typename U>
	static std::true_type check_type(typename U::capacity_type *);
	static std::false_type check_type(...);
	template <typename U>
	static auto check_member(const U& x)
		-> decltype(x.capacity, std::true_type());
	static std::false_type check_member(...);
public:
	static const bool value =
		decltype(check_type<EdgeType>(nullptr))::value &&
		decltype(check_member(std::declval<EdgeType>()))::value;
};
}
namespace loquat {
template <typename EdgeType>
class adjacency_list {
public:
	using edge_type = EdgeType;
	using edge_list = std::vector<edge_type>;
private:
	std::vector<std::vector<EdgeType>> m_edges;
public:
	adjacency_list()
		: m_edges()
	{ }
	explicit adjacency_list(size_t n)
		: m_edges(n)
	{ }
	size_t size() const {
		return m_edges.size();
	}
	const edge_list& operator[](vertex_t u) const {
		return m_edges[u];
	}
	edge_list& operator[](vertex_t u){
		return m_edges[u];
	}
	template <typename... Args>
	void add_edge(vertex_t from, Args&&... args){
		m_edges[from].emplace_back(std::forward<Args>(args)...);
	}
	void add_edge(vertex_t from, const edge_type& e){
		m_edges[from].emplace_back(e);
	}
};
}
namespace loquat {
namespace detail {
template <typename EdgeType>
auto negate_weight(EdgeType& e)
	-> typename std::enable_if<has_weight<EdgeType>::value, void>::type
{
	e.weight = -e.weight;
}
template <typename EdgeType>
auto negate_weight(EdgeType&)
	-> typename std::enable_if<!has_weight<EdgeType>::value, void>::type
{ }
}
template <typename EdgeType>
struct residual_edge : public EdgeType {
	using base_type = EdgeType;
	size_t rev;
	residual_edge()
		: base_type()
		, rev(0)
	{ }
	template <typename... Args>
	residual_edge(vertex_t to, size_t rev, Args&&... args)
		: base_type(to, std::forward<Args>(args)...)
		, rev(rev)
	{ }
	residual_edge(const base_type& e, size_t rev)
		: base_type(e)
		, rev(rev)
	{ }
};
template <typename EdgeType>
adjacency_list<residual_edge<EdgeType>>
make_residual(const adjacency_list<EdgeType>& graph){
	using edge_type = EdgeType;
	using residual_type = residual_edge<edge_type>;
	using capacity_type = typename edge_type::capacity_type;
	const size_t n = graph.size();
	adjacency_list<residual_type> result(n);
	for(vertex_t u = 0; u < n; ++u){
		for(const auto& e : graph[u]){
			result.add_edge(u, residual_type(e, 0));
		}
	}
	for(vertex_t u = 0; u < n; ++u){
		const size_t m = graph[u].size();
		for(size_t i = 0; i < m; ++i){
			auto e = graph[u][i];
			const auto v = e.to;
			e.to = u;
			e.capacity = capacity_type();
			detail::negate_weight(e);
			result[u][i].rev = result[v].size();
			result.add_edge(v, residual_type(e, i));
		}
	}
	return result;
}
}
namespace loquat {
template <typename EdgeType, typename Predicate>
adjacency_list<EdgeType> filter(
	const adjacency_list<EdgeType>& graph,
	Predicate pred)
{
	const size_t n = graph.size();
	adjacency_list<EdgeType> result(n);
	for(vertex_t u = 0; u < n; ++u){
		for(const auto& e : graph[u]){
			if(pred(u, e)){ result.add_edge(u, e); }
		}
	}
	return result;
}
}
namespace loquat {
template <typename T>
constexpr inline auto positive_infinity() noexcept
	-> typename std::enable_if<std::is_integral<T>::value, T>::type
{
	return std::numeric_limits<T>::max();
}
template <typename T>
constexpr inline auto negative_infinity() noexcept
	-> typename std::enable_if<std::is_integral<T>::value, T>::type
{
	return std::numeric_limits<T>::min();
}
template <typename T>
constexpr inline auto is_positive_infinity(T x) noexcept
	-> typename std::enable_if<std::is_integral<T>::value, bool>::type
{
	return x == std::numeric_limits<T>::max();
}
template <typename T>
constexpr inline auto is_negative_infinity(T x) noexcept
	-> typename std::enable_if<std::is_integral<T>::value, bool>::type
{
	return x == std::numeric_limits<T>::min();
}
template <typename T>
constexpr inline auto positive_infinity() noexcept
	-> typename std::enable_if<std::is_floating_point<T>::value, T>::type
{
	return std::numeric_limits<T>::infinity();
}
template <typename T>
constexpr inline auto negative_infinity() noexcept
	-> typename std::enable_if<std::is_floating_point<T>::value, T>::type
{
	return -std::numeric_limits<T>::infinity();
}
template <typename T>
inline auto is_positive_infinity(T x) noexcept
	-> typename std::enable_if<std::is_floating_point<T>::value, bool>::type
{
	return (x > 0) && std::isinf(x);
}
template <typename T>
inline auto is_negative_infinity(T x) noexcept
	-> typename std::enable_if<std::is_floating_point<T>::value, bool>::type
{
	return (x < 0) && std::isinf(x);
}
}
namespace loquat {
class no_solution_error : public std::runtime_error {
public:
	explicit no_solution_error(const char *what)
		: std::runtime_error(what)
	{ }
	explicit no_solution_error(const std::string& what)
		: std::runtime_error(what)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
std::vector<typename EdgeType::weight_type>
sssp_bellman_ford(vertex_t source, const adjacency_list<EdgeType>& graph){
	using weight_type = typename EdgeType::weight_type;
	const auto inf = positive_infinity<weight_type>();
	const auto n = graph.size();
	std::vector<weight_type> result(n, inf);
	result[source] = weight_type();
	bool finished = false;
	for(size_t iter = 0; !finished && iter < n; ++iter){
		finished = true;
		for(loquat::vertex_t u = 0; u < n; ++u){
			if(loquat::is_positive_infinity(result[u])){ continue; }
			for(const auto& e : graph[u]){
				const auto v = e.to;
				if(result[u] + e.weight < result[v]){
					result[v] = result[u] + e.weight;
					finished = false;
				}
			}
		}
	}
	if(!finished){
		throw no_solution_error("graph has a negative cycle");
	}
	return result;
}
}
namespace loquat {
template <typename EdgeType>
typename EdgeType::weight_type
mincostflow_primal_dual(
	typename EdgeType::capacity_type flow,
	vertex_t source,
	vertex_t sink,
	adjacency_list<EdgeType>& graph)
{
	using edge_type = EdgeType;
	using weight_type = typename edge_type::weight_type;
	const auto inf = positive_infinity<weight_type>();
	const auto n = graph.size();
	const auto predicate =
		[](vertex_t, const edge_type& e) -> bool { return e.capacity > 0; };
	auto h = sssp_bellman_ford(source, filter(graph, predicate));
	std::vector<vertex_t> prev_vertex(n);
	std::vector<size_t> prev_edge(n);
	weight_type result = 0;
	while(flow > 0){
		using pair_type = std::pair<weight_type, vertex_t>;
		std::priority_queue<
			pair_type, std::vector<pair_type>, std::greater<pair_type>> pq;
		std::vector<weight_type> d(n, inf);
		pq.emplace(0, source);
		d[source] = weight_type();
		while(!pq.empty()){
			const auto p = pq.top();
			pq.pop();
			const auto u = p.second;
			if(d[u] < p.first){ continue; }
			for(size_t i = 0; i < graph[u].size(); ++i){
				const auto& e = graph[u][i];
				if(e.capacity <= 0){ continue; }
				const auto v = e.to;
				const auto t = d[u] + e.weight + h[u] - h[v];
				if(d[v] <= t){ continue; }
				d[v] = t;
				prev_vertex[v] = u;
				prev_edge[v] = i;
				pq.emplace(t, v);
			}
		}
		if(is_positive_infinity(d[sink])){
			throw no_solution_error("there are no enough capacities to flow");
		}
		for(size_t i = 0; i < n; ++i){ h[i] += d[i]; }
		weight_type f = flow;
		for(vertex_t v = sink; v != source; v = prev_vertex[v]){
			const auto u = prev_vertex[v];
			f = std::min(f, graph[u][prev_edge[v]].capacity);
		}
		flow -= f;
		result += f * h[sink];
		for(vertex_t v = sink; v != source; v = prev_vertex[v]){
			const auto u = prev_vertex[v];
			auto& e = graph[u][prev_edge[v]];
			e.capacity -= f;
			graph[v][e.rev].capacity += f;
		}
	}
	return result;
}
}
using namespace std;
using edge = loquat::edge<
	loquat::edge_param::weight<int>,
	loquat::edge_param::capacity<int>>;
int main(){
	ios_base::sync_with_stdio(false);
	int n, m, f;
	cin >> n >> m >> f;
	loquat::adjacency_list<edge> g(n);
	for(int i = 0; i < m; ++i){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		g.add_edge(a, b, d, c);
	}
	const int source = 0, sink = n - 1;
	auto residual = loquat::make_residual(g);
	try{
		const auto answer =
			loquat::mincostflow_primal_dual(f, source, sink, residual);
		cout << answer << endl;
	}catch(loquat::no_solution_error){
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3284