### 问题描述 给定一张有向图，每条边存在 $4$ 个参数 $(u,v,c,w)$，表示该边的起点为 $u$，终点为 $v$，流量容量为 $c$，每扩容该边 $1$ 的容量，费用为 $w$。 假设原图中 $1$ 至 $n$ 的最大流为 $flow$，请你求解 $1$ 至 $n$ 的最大流增加为 $flow+k$，需要花费的最小扩容费用之和。 ### 输入格式 第一行包含 $3$ 个正整数 $n,m,k$，表示图的点数，边数和需要增加的流量。 之后 $m$ 行，第 $i$ 行给定 $4$ 个正整数，分别表示 $u,v,c,w$。 ### 输出格式 输出共一行，输出一个整数，表示答案。 ### 样例输入 ```text 5 6 2 1 2 5 8 2 5 9 9 5 1 6 2 5 1 1 8 1 2 8 7 2 5 4 9 ``` ### 样例输出 ```text 32 ``` ### 评测数据规模 对于所有测评数据，$1 \leq N,M,c,w \leq 100$。