题目描述

在星历 2012 年，星灵英雄 Zeratul 预测到他所在的 Aiur 行星在 $M$ 天后会发生持续性暴雨灾害，尤其是他们的首都。而 Zeratul 作为星灵族的英雄，当然是要尽自己最大的努力帮助星灵族渡过这场自然灾害。要渡过这场自然灾害，Zeratul 自然要安排很多很多事情，其中一件就是将雨水疏导到大海里去。星灵族在重建家园的时候建造了 $N$ 条河流，这些河流连接了共 $N+1$ 个城市，当然其中包括了星灵首都。城市的编号为 $0 \cdots N$，星灵首都的编号为 $0$。当然水流是有方向的，除了星灵首都以外，其余的城市都有且仅有一条河流流入。如果一个城市没有流出去的河流，那么这个城市就是一个沿海城市，可以认为流入这个城市的河流是直接流入大海的。聪明的星灵族在建造河流的时候是不会让其出现环状结构的，也就是说所有的河流都是能够流入大海的。每一条河流都是有一个最大流量的，一旦超过这个最大流量，就会发生洪水灾害。因此从星灵首都流入大海的总水流量是有一个最大值的。例如有 $3$ 条河流：第一条是从城市 $0$ 流向城市 $1$，最大流量为 $4$；第二条是从城市 $1$ 流向城市 $2$，最大流量为 $2$；第三条是从城市 $1$ 流向城市 $3$，最大流量为 $3$。此时从星灵首都（城市 $0$）流入大海的总水流量最大为 $4$。
方案有两种：

A.第一条河流的流量为 $4$，第二条河流的流量为 $2$，第三条河流的流量为 $2$。

B.第一条河流的流量为 $4$，第二条河流的流量为 $1$，第三条河流的流量为 $3$。

由于离暴雨到来还有时间，因此 Zeratul 可以扩大某些河流的最大流量来使得从星灵首都流入大海的总水流量增大。比如将上面这个例子的第一条河流的最大流量增大 $1$，那么从星灵首都流入大海的总流水量也可以增大 $1$，变成了 $5$。当然将河流的最大流量扩大是需要时间的，将一条河流的最大流量扩大 $1$ 所需要的时间为 $1$ 天。离暴雨到来还有 $M$ 天，因此 Zeratul 也有 $M$ 天的时间来扩大河流的最大流量。不过由于河流周围的地形限制，每条河流并不是能够无限扩大的，因此每条河流的可以扩大到的最大流量也是有限制的。而此时 Zeratul 正忙着安排别的工作，因此他将这个艰巨的任务交给了你。你需要安排一种方案，使得从星灵首都流入大海的总水流量最大。不过现在你只需要告诉 Zeratul 这个最大值即可。

输入格式

第一行包含一个正整数 $N$ 和一个非负整数 $M$。其中 $N$ 表示河流的个数，$M$ 表示离暴雨到来还剩下的天数。
接下来 $N$ 行，每行四个正整数 $U,V,A,B$。其中 $U$ 和 $V$ 为该河流所连接的两个城市，且河流的水流方向为从城市 $U$ 流向城市 $V$，$A$ 和 $B$ 表示该河流当前的最大流量和可以扩大到的最大流量的上限。输入数据保证合法。

输出格式

仅包含一个整数，表示从星灵首都流入大海的最大总水流量。

样例输入

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

样例输出

11

样例说明

将第一条河流的最大流量扩大 $1$，变为 $5$。将第二条河流的最大流量扩大 $5$，变为 $6$。第三条河流的最大流量不扩大，仍然为 $2$。第四条河流的最大流量不扩大，仍然为 $3$。第五条河流的最大流量不扩大，仍然为 $6$。此时从星灵首都流入大海的总水流量为 $6+3+2=11$。

数据规模与约定

对于 $100\%$ 的数据，$1\leq A\leq B\leq 1\times10^5$，$N \leq 1\times10^4$，$M\leq 1\times10^6$。

题目来源

版权所有者：潘宇超