Minimum Cost Flow

Find the minimum cost to send a certain amount of flow through a flow network.

The flow network is a directed graph where each edge $e$ has capacity $c(e)$ and cost $d(e)$. Each edge $e$ can send an amount of flow $f(e)$ where $f(e) \leq c(e)$. Find the minimum value of $\sum_{e} (f(e) \times d(e))$ to send an amount of flow $F$ from source $s$ to sink $t$.

Input

A flow network $G(V,E)$ is given in the following format.

$|V|\;|E|\;F$
$u_0\;v_0\;c_0\;d_0$
$u_1\;v_1\;c_1\;d_1$
:
$u_{|E|1}\;v_{|E|-1}\;c_{|E|-1}\;d_{|E|-1}$

$|V|$, $|E|$, $F$ are the number of vertices, the number of edges, and the amount of flow of the flow network respectively. The vertices in $G$ are named with the numbers $0, 1,..., |V|−1$. The source is $0$ and the sink is $|V|−1$.

$u_i$, $v_i$, $c_i$, $d_i$ represent $i$-th edge of the flow network. A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$, and $c_i$ and $d_i$ are the capacity and the cost of $i$-th edge respectively.

Output

Print the minimum value in a line. If it is impossible to send the flow from the source $s$ to the sink $t$, print -1.

Constraints

• 2 ≤ $|V|$ ≤ 100
• 1 ≤ $|E|$ ≤ 1000
• 0 ≤ $F$ ≤ 1000
• 0 ≤ $c_i$, $d_i$ ≤ 1000
• $u_i$ $\ne$ $v_i$
• If there is an edge from vertex $x$ to vertex $y$, there is no edge from vertex $y$ to vertex $x$.

Sample Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1

Sample Output

6

---