#1782. 防御

防御

题目描述

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

n1n-1 条通道上的任何一条都可以布防:每条通道 ii 有两个属性 ai,bia_i, b_i ,表示通道上布防的兵力值 wiw_i 受到约束 aiwibia_i \leq w_i \leq b_i 。现在你的手头上总共有 mm 个兵力值,将要对所有条通道进行布防。

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

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

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

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

输入格式

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

22​​ 到 nn​​ 行每行四个正整数 ui,vi,ai,biu_i, v_i, a_i, b_i​ ,第 ii​ 行的数据描述了第 i1i - 1​ 条通道的信息:连接编号为 uiu_i​ 和 viv_i​ 的要塞,至少布防 aia_i​ 兵力值,至多布防 bib_i 兵力值。

输出格式

一行一个整数 xx , 表示敌人至少需要 xx 的兵力可以找到一种方案攻到 11 号。

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%30\% 的数据: 1n,b,m101 \leq n, b, m \leq 10

  • 对于另外 10%10\% 的数据:除了 11 号要塞和 22 号要塞以外,剩下的要塞只与两个要塞相连。

  • 对于 100%100\% 的数据: 1n2×105,1ab109,am10141 \leq n \leq 2 \times 10^5, 1 \leq a \leq b \leq 10^9, \sum a \leq m \leq 10 ^ {14}

大样例

大样例下载