题目描述

现有 $n$ 个要塞，其中 $1$ 号要塞为核心。这 $n$ 个要塞由 $n - 1$ 条双向通道相连，使得这些要塞两两相互可达，你可以认为这些要塞是一个以 1 号结点为根的树结构。

在 $n-1$ 条通道上的任何一条都可以布防：每条通道 $i$ 有两个属性 $a_i, b_i$ ，表示通道上布防的兵力值 $w_i$ 受到约束 $a_i \leq w_i \leq b_i$ 。现在你的手头上总共有 $m$ 个兵力值，将要对所有条通道进行布防。

敌人只能任选一个或一些叶子结点发起进攻，他们的目标是攻到 $1$ 号要塞（树的根）。假设有一股兵力值为 $x$ 的敌人，他们要经过一条布防为 $w$ 兵力值的通道，如果 $x>w$，那么这个通道被攻破，敌人的兵力值变为 $x-w$；否则敌人被击溃，无法通过这个通道，同时这个通道的兵力值会被敌人消耗到 $w-x$。如果有任意一个敌人攻到 $1$ 号要塞则防守失败，否则防守成功。

敌人的兵力值刚好等于布防的兵力值时，视为敌人无法通过该通道。

敌人的兵力值是有限的，他们能够将兵力值分配投放到最外围的任意个要塞（叶子结点），然后向 $1$ 号要塞发起进攻。

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

输入格式

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

第 $2$​​ 到 $n$​​ 行每行四个正整数 $u_i, v_i, a_i, b_i$​ ，第 $i$​ 行的数据描述了第 $i - 1$​ 条通道的信息：连接编号为 $u_i$​ 和 $v_i$​ 的要塞，至少布防 $a_i$​ 兵力值，至多布防 $b_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 \leq n, b, m \leq 10$ 。

• 对于另外 $10\%$ 的数据：除了 $1$ 号要塞和 $2$ 号要塞以外，剩下的要塞只与两个要塞相连。

• 对于 $100\%$ 的数据： $1 \leq n \leq 2 \times 10^5, 1 \leq a \leq b \leq 10^9, \sum a \leq m \leq 10 ^ {14}$ 。

大样例

大样例下载