说明

在实际应用中，不仅要考虑流量，还要考虑费用。例如在网络布线工程中有很多中电缆，电缆的粗细不同，流量和费用也不同。如果全部使用较粗的电缆，则造价太高；如果全部使用较细的电缆，则流量满足不了要求。我们希望建立一个费用最小、流量最大的网络，即最小费用最大流。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入结点个数n和边数m（1<=n<=50，1<=m<=2500）。

接下来m行，每行4个数，两个结点u，v及边（u--v）的容量w,单位容量费用c（1<=u,v<=50，1<=w,c<=100）。

输出格式

对于每一组输入，输出网络的最小费用和最大流值。

每组的输出占一行。

样例

1
6 10
1 3 4 7
1 2 3 1
2 5 4 5
2 4 6 4
2 3 1 1
3 5 3 6
3 4 5 3
4 6 7 6
5 6 3 2
5 4 3 3

88 7

来源

《趣学算法》7.4节