该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在疆域的边境线上，若干要塞通过防御通道相互连接，以守护核心要塞的安全。为了抵御从外围叶子要塞发起的进攻，守军需要在每条通道上布置一定兵力作为路障。你手中拥有有限的总兵力，需要合理分配到各条通道上，使得敌军投入最少的兵力也无法突破到中心要塞。

题目描述

现有 $n$ 个要塞，其中 $1$ 号要塞为核心。这 $n$ 个要塞由 $n-1$ 条双向通道相连，构成一棵以 $1$ 号结点为根的树结构。在第 $i$ 条通道上可以布防兵力值 $w_i$，且满足约束

你手头上总共有 $m$ 个兵力值，需要分配到所有通道上完成布防。

敌人只能从任意一个或多个叶子结点发起进攻，他们的目标是攻到 $1$ 号要塞。假设一支敌军的兵力值为 $x$，经过一条布防为 $w$ 的通道：

• 若 $x > w$，该通道被攻破，敌军剩余兵力变为 $x - w$；
• 若 $x \le w$，敌军被击溃，无法通过该通道，同时通道上的守军损耗至 $w - x$。

只要有任意一支敌军能够抵达 $1$ 号要塞，防守即告失败；否则防守成功。敌人可将其总兵力分配到若干叶子结点，分别从这些点发起攻击。

请在守军布防最优的情况下，评估敌人至少需要多少总兵力才能攻到 $1$ 号要塞。

输入格式

第 1 行包含两个正整数 $n, m$，分别表示要塞的个数和你的总兵力值，保证至少存在一种合法布防方案。

第 $2$ 行到第 $n$ 行每行四个正整数 $u_i, v_i, a_i, b_i$，第 $i$ 行（$2 \le i \le n$）描述了第 $i-1$ 条通道的信息：连接编号为 $u_i$ 和 $v_i$ 的要塞，该通道上布防的兵力值 $w_i$ 满足

输出格式

输出一个整数 $x$，表示敌人至少需要 $x$ 的兵力才能找到一种方案攻到 $1$ 号要塞。

样例

11 50
5 4 2 40
3 7 3 5
7 6 6 20
1 2 2 8
9 2 3 20
10 2 2 40
5 11 2 5
4 8 7 8
1 7 1 2
1 5 1 5

8

样例解释

无

数据范围

• 对于 $30\%$ 的数据：$1 \le n, b_i, m \le 10$。
• 对于另 $10\%$ 的数据：除 $1$ 号要塞和 $2$ 号要塞以外，其余要塞度数不超过 $2$。
• 对于 $100\%$ 的数据：$1 \le n \le 2\times10^5,\ 1 \le a_i \le b_i \le 10^9,\ \sum_i a_i \le m \le 10^{14}$.