题目描述

给定 $n$ 个点，$m$ 条边，给定每条边的容量和单位流量需要支付的费用，求点 $1$ 到点 $n$ 的最大流以及此时需要的最小费用。

注意，图可能存在重边。

输入格式

第一行两个整数 $n$、$m$，表示有 $n$ 个点 $m$ 条边。

从第二行开始的之后 $m$ 行，每行四个整数 $s_i$、$t_i$、$c_i$、$w_i$ 表示一条从 $s_i$ 到 $t_i$ 的边，容量为 $c_i$，单位流量需要支付的费用为 $w_i$。

输出格式

输出一行两个整数，表示最大流和最小费用。

8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0

6 24

10 30
1 9 23 2
9 6 29 8
2 8 22 20
7 3 10 16
3 10 18 19
1 2 18 29
9 8 18 15
4 10 5 12
7 5 30 12
7 8 29 7
9 5 20 26
9 4 15 5
9 10 21 6
9 8 15 8
3 4 10 7
3 10 2 5
3 10 26 6
9 3 11 14
6 4 11 7
2 5 1 20
9 5 1 1
6 10 10 17
8 10 29 5
9 4 10 22
5 10 3 14
8 5 16 25
7 10 21 25
1 9 11 16
1 2 14 15
7 9 30 25

57 1594

10 30
7 4 7 19
9 10 6 12
6 4 13 2
3 5 18 21
8 10 12 4
9 4 11 1
2 5 23 2
2 10 2 7
6 5 13 22
8 5 2 10
5 7 12 14
6 5 22 17
5 10 27 23
1 6 1 21
2 7 30 16
4 5 17 12
1 3 27 25
2 7 19 27
1 9 18 25
4 7 30 28
6 10 20 16
1 2 16 21
3 5 26 2
1 9 1 4
1 2 6 7
2 9 25 28
3 8 11 2
2 3 9 14
9 4 16 2
1 7 3 15

47 1821

提示

对于所有数据，保证 $1 \le n \le 400$，$0 \le m \le 15000$，$0 \le w_i \le 2 ^ {31} - 1$，保证答案在 32 位有符号整数范围内。

本题数据较弱，不存在最小费用最大流的极限情况。

实现时，若使用 Bellman-Ford 算法可以考虑如下优化：若在某次迭代中所有 $\pi(i)$ 均保持不变，则不继续迭代。