测试数据来自 system/1885

背景

只有一个心愿 我想帮助你 寻找吧
——Fay

描述

Phorni 是一个音之妖精，在窗台上坐着时，偶然看到一棵树。
阳光透过玻璃，在房间中散发出芳幽的气息。
在等着Velding 回来的Phorni 准备去看看隔壁电子工程系的学生在干什么，偶然想到了费用流。
假定树根是源点，每个叶子连向汇点一条流量为正无穷，费用为0 的边，对这棵树求费用流。

格式

输入格式

输入共N 行。
第一行，一个整数N ，树中节点的个数，其中1 号节点是根。
接下来N -1 行，每行四个整数，Xi. Yi, Capi, Costi 。表示有一条从Xi 到Yi ，容量为Capi ，费用为Costi 的边。

输出格式

输出共两行。
第一行，一个整数，表示树上的最大流。
第二行，一个整数，表示最大流时树上的最小费用。

样例1

样例输入1

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

样例输出1

5
27

限制

对于10% 的数据，数据保证是用某种方式随机生成的。
对于100% 的数据，1  <= N <=  100000
1  <= Xi, Yi <= N
1 <= Capi <= 400000
0 <= Costi <= 1000
答案保证可以用32 位带符号整数类型存下。

来源

Disillusioning #1 水题+原题赛