[2009国家集训队]拯救Protoss的故乡

在星历 $2012$ 年，星灵英雄 Zeratul 预测到，他所在的 Aiur 行星将在 $M$ 天后遭遇持续性暴雨，首都受到的威胁尤其严重。为了帮助星灵族渡过这场自然灾害，Zeratul 需要将雨水通过河流疏导至大海。

星灵族在重建家园时修建了 $N$ 条河流，连接了 $N+1$ 个城市。城市编号为 $0$ 至 $N$ ，其中编号为 $0$ 的城市是星灵首都。每条河流中的水都有固定的流动方向。除星灵首都外，每个城市都有且仅有一条河流流入。如果一个城市没有流出的河流，那么它就是沿海城市，可以认为流入该城市的水会直接流入大海。

河流网络中不存在环，因此所有河流中的水最终都能流入大海。

每条河流都有一个最大流量。一旦实际流量超过最大流量，就会发生洪水灾害。因此，从星灵首都流入大海的总水流量存在一个最大值。

例如，共有 $3$ 条河流：

第 $1$ 条河流从城市 $0$ 流向城市 $1$ ，最大流量为 $4$ ；
第 $2$ 条河流从城市 $1$ 流向城市 $2$ ，最大流量为 $2$ ；
第 $3$ 条河流从城市 $1$ 流向城市 $3$ ，最大流量为 $3$ 。

此时，从星灵首都流入大海的总水流量最大为 $4$ 。一种方案是令这 $3$ 条河流的流量依次为 $4$ 、 $2$ 、 $2$ ；另一种方案是令它们的流量依次为 $4$ 、 $1$ 、 $3$ 。

在暴雨到来前，Zeratul 可以扩大部分河流的最大流量，从而提高星灵首都的排水能力。将一条河流的最大流量扩大 $1$ ，需要花费 $1$ 天。例如，将上述第 $1$ 条河流的最大流量扩大 $1$ ，从星灵首都流入大海的最大总水流量也会增加 $1$ ，变为 $5$ 。

距离暴雨到来还有 $M$ 天，因此 Zeratul 最多可以花费 $M$ 天扩大河流。由于周围地形的限制，每条河流的最大流量都只能扩大到给定的上限。

请安排河流的扩建方案，使从星灵首都流入大海的总水流量最大，并输出这个最大值。

输入格式

第一行包含一个正整数 $N$ 和一个非负整数 $M$ ，分别表示河流数量和距离暴雨到来还剩下的天数。

接下来 $N$ 行，每行包含 $4$ 个整数 $U,V,A,B$ ，表示一条从城市 $U$ 流向城市 $V$ 的河流。该河流当前的最大流量为 $A$ ，可以扩大到的最大流量上限为 $B$ 。

输入数据保证合法。

输出格式

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

样例输入

样例输出

样例解释

将第 $1$ 条河流的最大流量扩大 $1$ ，使其变为 $5$ ；将第 $2$ 条河流的最大流量扩大 $5$ ，使其变为 $6$ 。其余河流不进行扩建，最大流量依次保持为 $2$ 、 $3$ 、 $6$ 。

扩建共花费 $1+5=6$ 天，不超过剩余的 $7$ 天。此时从星灵首都流入大海的最大总水流量为

6+3+2=11。

数据范围

$1\le A\le B\le 10^5$ ；
$N\le 10^4$ ；
$M\le 10^6$ 。

来源与许可

本题为 $2009$ 年国家集训队试题「拯救 Protoss 的故乡」，题面与测试数据整理自 BZOJ $2040$ 。

样例 1

输入