【题目描述】：
    在星历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这个最大值即可。
【题目解法】：
    很好的题目orz
    考虑网络流，连边(x,y,A,0) (x,y,B-A,1)
    不断增广，直到费用等于m为止（当然可能无法继续增加）
    这样做显然TLE
    考虑用树链剖分+dfs序维护这棵树
    一棵线段树维护链上容量最小值，另一棵线段树维护叶子结点的费用最小值
    一开始所有边的费用为0，容量为A
    每次找到费用最小的叶子节点，然后将他到树根的路径上所有边的权值减去最小值
    然后我们找出所有边权=0的边
    1.如果他本来是费用为0的，我们将他改为1，容量B-A，并且对应修改他所控制的叶子节点
    2.如果他本来的费用为1，我们将他的容量改为INF，然后对应控制的叶子节点费用也变成INF
    注意特殊处理一些细节：
    1.最后一次增广不一定可以将一条链上的容量全部增广
    2.最后不一定可以将所有费用用完
    3.为了方便我们可以将边的权值下放到下面的结点，将根节点的权值变成INF即可
    复杂度O(N log N log N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=10005;
const int INF=1e9;
struct edge {int x,next;} b[N];
struct point {int base,expand;} c[N];
int n,m,tot,a[N],cnt,fa[N],size[N],L[N],R[N];
int son[N],top[N],id[N],dep[N],ans,cost;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void addedge(int x,int y)
{
    ++tot;
    b[tot].x=y;
    b[tot].next=a[x];
    a[x]=tot;
}
void init()
{
    n=getint()+1; m=getint(); dep[1]=1;
    for (int i=1; i<n; i++)
    {
        int x=getint()+1,y=getint()+1,A=getint(),B=getint();
        c[y].base=A; c[y].expand=B-A; addedge(x,y); fa[y]=x;
    }
    c[1].base=c[1].expand=INF;
}
void dfs(int x)
{
    size[x]=1; int k=0;
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x; dep[pp]=dep[x]+1; dfs(pp);
        if (size[pp]>k) k=size[pp],son[x]=pp; size[x]+=size[pp];
    }
}
void dfs(int x,int anc)
{
    top[x]=anc; L[x]=++cnt; id[cnt]=x; if (son[x]) dfs(son[x],anc);
    for (int p=a[x];p;p=b[p].next) if (b[p].x!=son[x]) dfs(b[p].x,b[p].x); R[x]=cnt;
}
namespace Leaf
{
    struct node {int mint,id,lazy;} tree[N*4];
    inline void tag(int p,int x)
    {
        if (tree[p].mint>=INF) return;
        tree[p].mint+=x; tree[p].lazy+=x;
    }
    inline void lazy_tag(int p)
    {
        if (tree[p].lazy==0) return;
        tag(p*2,tree[p].lazy); tag(p*2+1,tree[p].lazy);
        tree[p].lazy=0;
    }
    inline void updata(int p)
    {
        int lc=p*2,rc=p*2+1;
        tree[p].mint=min(tree[lc].mint,tree[rc].mint);
        tree[p].id=(tree[p].mint==tree[lc].mint)?tree[lc].id:tree[rc].id;
    }
    void build(int p,int l,int r)
    {
        if (l==r) {tree[p].id=l; tree[p].mint=(size[id[l]]==1)?0:INF; return;}
        int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); updata(p);
    }
    void modify(int p,int l,int r,int ll,int rr,int x)
    {
        if (l!=r) lazy_tag(p); int mid=(l+r)/2;
        if ((l==ll)&&(r==rr)) {tag(p,x); return;}
        if (rr<=mid) modify(p*2,l,mid,ll,rr,x);
        else if (ll>mid) modify(p*2+1,mid+1,r,ll,rr,x);
        else modify(p*2,l,mid,ll,mid,x),modify(p*2+1,mid+1,r,mid+1,rr,x);
        updata(p);
    }
}
namespace Chain
{
    struct node {int mint,lazy; bool flag;} tree[N*4];
    inline void tag(int p,int x)
    {
        if (tree[p].mint>=INF) return;
        tree[p].lazy+=x; tree[p].mint+=x;
    }
    inline void lazy_tag(int p)
    {
        if (tree[p].lazy==0) return;
        tag(p*2,tree[p].lazy); tag(p*2+1,tree[p].lazy);
        tree[p].lazy=0;
    }
    void build(int p,int l,int r)
    {
        if (l==r) {tree[p].mint=c[id[l]].base; return;}
        int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r);
        tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
    }
    void modify(int p,int l,int r,int ll,int rr,int x)
    {
        if (l!=r) lazy_tag(p); int mid=(l+r)/2;
        if ((l==ll)&&(r==rr)) {tag(p,x); return;}
        if (rr<=mid) modify(p*2,l,mid,ll,rr,x);
        else if (ll>mid) modify(p*2+1,mid+1,r,ll,rr,x);
        else modify(p*2,l,mid,ll,mid,x),modify(p*2+1,mid+1,r,mid+1,rr,x);
        tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
    }
    int ask(int p,int l,int r,int ll,int rr)
    {
        if (l!=r) lazy_tag(p); int mid=(l+r)/2;
        if ((l==ll)&&(r==rr)) return tree[p].mint;
        if (rr<=mid) return ask(p*2,l,mid,ll,rr);
        else if (ll>mid) return ask(p*2+1,mid+1,r,ll,rr);
        else return min(ask(p*2,l,mid,ll,mid),ask(p*2+1,mid+1,r,mid+1,rr));
    }
    void modify(int p,int l,int r)
    {
        if (l!=r) lazy_tag(p); int mid=(l+r)/2;
        if (tree[p].mint!=0) return;
        if (l==r)
        {
            if (tree[p].flag==false)
            {
                tree[p].mint=c[id[l]].expand;
                Leaf::modify(1,1,n,L[id[l]],R[id[l]],1);
                tree[p].flag=true; return;
            }
            Leaf::modify(1,1,n,L[id[l]],R[id[l]],INF);
            tree[p].mint=INF; return;
        }
        modify(p*2,l,mid); modify(p*2+1,mid+1,r);
        tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
    }
    void modify(int p,int l,int r,int ll,int rr)
    {
        if (l!=r) lazy_tag(p); int mid=(l+r)/2;
        if ((l==ll)&&(r==rr)) {modify(p,l,r); return;}
        if (rr<=mid) modify(p*2,l,mid,ll,rr);
        else if (ll>mid) modify(p*2+1,mid+1,r,ll,rr);
        else modify(p*2,l,mid,ll,mid),modify(p*2+1,mid+1,r,mid+1,rr);
        tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
    }
    int ask(int x)
    {
        int nowans=INF;
        for (;x;x=fa[top[x]]) nowans=min(nowans,ask(1,1,n,L[top[x]],L[x]));
        return nowans;
    }
    void modify(int x,int mint)
    {
        for (int p=x;p;p=fa[top[p]]) modify(1,1,n,L[top[p]],L[p],-mint);
        for (;x;x=fa[top[x]]) modify(1,1,n,L[top[x]],L[x]);
    }
}
void build()
{
    dfs(1); dfs(1,1);
    Leaf::build(1,1,n);
    Chain::build(1,1,n);
}
void solve()
{
    for (cost=0; cost<=m;)
    {
        int now=Leaf::tree[1].id; now=id[now];
        int flow=Chain::ask(now),Cost=Leaf::tree[1].mint;
        if (Cost==INF) break; if (Cost+cost>m) break;
        if (Cost!=0) flow=min(flow,(m-cost)/Cost);
        Chain::modify(now,flow); ans+=flow; cost+=flow*Cost;
    }
    printf("%d\n",ans);
}
int main()
{
    init();
    build();
    solve();
    return 0;
}