最小費用流

各辺にコストが設定されたフローネットワークにおいて、始点 $s$ から終点 $t$ まで流量 $F$ のフローを流すための最小コストを求めてください。

フローネットワークの各辺 $e$ には容量 $c(e)$ 及びコスト $d(e)$ が設定されています。各辺 $e$ には容量 $c(e)$ を超えない流量 $f(e)$ のフローを流すことができます。始点 $s$ から終点 $t$ へ流量 $F$ のフローを流したときの、$\sum_{e} (f(e) \times d(e))$ の最小値を求めてください。

入力

フローネットワーク $G(V,E)$ が以下の形式で与えられる。

$|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$ はそれぞれフローネットワーク $G$ の頂点の数、辺の数、流したい流量を示す。 $G$ の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられており、始点を 0、終点を $|V|-1$ とする。

$u_i$, $v_i$, $c_i$, $d_i$ はフローネットワーク $G$ の $i$ 番目の辺を表し、頂点 $u_i$ から頂点 $v_i$ に向かって容量が $c_i$ でコストが $d_i$ の辺があることを表す。

出力

最小値を１行に出力する。ただし、始点 $s$ から終点 $t$ へ流量 $F$ のフローを流すことができない場合は -1 を１行に出力する。

制約

• 2 ≤ $|V|$ ≤ 100
• 1 ≤ $|E|$ ≤ 1000
• 0 ≤ $F$ ≤ 1000
• 0 ≤ $c_i$, $d_i$ ≤ 1000
• $u_i$ $\ne$ $v_i$
• 頂点 $x$ から頂点 $y$ に向かって辺がある場合、頂点 $y$ から頂点 $x$ に向かう辺（逆辺）はない。

入力例

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

出力例

6

---