6040: BZOJ2040：[2009国家集训队]拯救Protoss的故乡

在星历2012年，星灵英雄Zeratul预测到他所在的Aiur行星在M天后会发生持续性暴雨灾害，尤其是他们的首都。而Zeratul作为星灵族的英雄，当然是要尽自己最大的努力帮助星灵族渡过这场自然灾害。要渡过这场自然灾害，Zeratul自然要安排很多很多事情，其中一件就是将雨水疏导到大海里去。星灵族在重建家园的时候建造了N条河流，这些河流连接了共N+1个城市，当然其中包括了星灵首都。城市的编号为0…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。 1≤A≤B≤100000 N< = 10000 M< = 1000000

题目来源

版权所有者： 潘宇超