F - 最小費用流 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

V個の街があります。各街には1,2,...,Vと番号が付いています。E本の水道管があり、i本目の水道管は街u_iから街v_iへ水を最大でc_iだけ流すことができますが、水を1流すごとに費用がd_iかかります。街1から街Vへ水をFだけ流すとき、合計費用の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられます。

V E F
u_1 v_1 c_1 d_1
u_2 v_2 c_2 d_2
\vdots
u_E v_E c_E d_E

出力

街1から街Vへ水をFだけ流した時の合計費用の最小値を出力せよ。

制約

  • 入力は全て整数
  • 1 \leq V, E \leq 100
  • 1 \leq F \leq 10^{9}
  • 1 \leq u_i, v_i \leq V (1 \leq i \leq E)
  • 1 \leq c_i, d_i \leq 10^{9} (1 \leq i \leq E)

  • v_i \neq u_i (1 \leq i \leq E)

入力例 

6 9 3
1 2 3 2
1 3 2 1
2 3 2 2
2 4 3 4
3 4 5 1
3 5 6 2
4 5 2 2
4 6 6 3
5 6 10 2

出力例 

18