9607 - 网络扩容

给定一张有向图，每条边都有一个容量 c 和一个扩容费用 w。这里扩容费用是指将容量扩大 1 所需的费用。求：

  1. 在不扩容的情况下，1 到 n 的最大流；

  2. 将 1 到 n 的最大流增加 k 所需的最小扩容费用。

输入

第一行包含三个整数 n,m,k，表示有向图的点数、边数以及所需要增加的流量。

接下来的 M 行每行包含四个整数 u,v,c,w，表示一条从u 到 v，容量为 c，扩容费用为 w 的边。

输出

输出文件一行包含两个整数，分别表示问题 1 和问题 2 的答案。

样例

输入

5 8 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
1 2 1 1
1 4 2 1

输出

13 19

提示

  • 对于 100\% 的数据，保证 1\le n\le 10^3，1\le m\le 5\times 10^3，1\le k\le 10，1 \leq u, v \leq n，1\le c,w\le 100。

来源

浙江省选

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题