问题 5038 --果子采摘

5038: 果子采摘

题目描述

  az正准备摘下树上的果实。
这棵树共有 $n$ 个节点,其中 $1$ 号节点为根,树上每一个节点有一颗果实,每一颗果实有一定的美味度 $V_i$,同时有一定的毒素 $P_i$ 。
az要想摘下树上的某一颗果实当且仅当这个果实的父节点被选择,当摘下某一颗果实时,az会获得这棵果实的美味度,同时也会中这颗果实的毒,az最多能接受的毒为  $m$,现在az希望在不中毒太深的情况下获得最大的美味度。
az不知道该怎么办了,希望你能帮帮他。

输入

输入数据的第一行包含两个由空格隔开的整数 $n,m$ 。
接下来 $n$ 行,每行两个空格隔开的整数 $V_i,P_i$ ,表示 $i$ 号果实的美味度和毒素。
再接下来 $n-1$ ,每行两个整数,$u$ 表示 $v$ 之间有连边。

输出

输出仅一行一个整数,表示az在不超过毒素上限的情况下能够获得的最大美味度。

样例输入输出

输入#1 复制
7 9
39 6
13 2
22 6
7 4
19 5
28 6
-17 1
2 1
3 2
4 1
5 4
6 2
7 3
输出#1 复制
52

提示

对于 $20\%$ 的数据,树的形态是一条链;
对于 $50\%$ 的数据,$1 \leq n,m \leq 500$;
对于 $100\%$ 的数据: $1\leq n,m \leq 2000$ , $1 \leq |V_i| \leq 10^4$ , $ 1\leq P_i \leq 10^4$。

序号 标题 作者 发表时间 费用 订购数 操作