Flariana 花和熊蜂构成了雨林中最美好的伙伴关系之一。春天，几朵花盛开并开始产生花粉。特殊的藤蔓在花朵之间形成了桥梁网络。通过这些藤蔓，从任意一朵花到另一朵花都有且仅有一条路径。

每朵花上都有一个蜂群。这个蜂群保护着所有接触该花朵的藤蔓。这意味着每条藤蔓都由两个蜂群共同保护。位于花朵 $k$ 上的蜂群由 $s_k$ 只蜜蜂组成，并具有 $p_k$ 的授粉能力。

有一天，一只侦察蜂宣布在山那边发现了一片新的花丛，它们需要一群蜜蜂去帮助授粉。

作为蜂王，你必须选择一组蜂群去执行任务。对于每一条藤蔓，当前保护它的两个蜂群中至少要有一个留下来，以确保藤蔓得到保护。被选中执行任务的蜂群中的所有蜜蜂都必须出发。你愿意派遣的蜜蜂总数最多为 $S$ 只。

请确定你能派遣去执行任务的蜂群所能提供的最大授粉能力总和。

输入格式

第一行包含整数 $N$ ($1 \le N \le 300$)，表示花朵的数量，以及 $S$ ($1 \le S \le 300$)，表示你可以派遣执行任务的蜜蜂最大数量。花朵编号为 $1$ 到 $N$。

接下来的 $N$ 行描述蜂群。每行包含两个整数 $s_k$ ($1 \le s_k \le 300$)，表示该蜂群中的蜜蜂数量，以及 $p_k$ ($1 \le p_k \le 100$)，表示该蜂群的授粉能力。

最后 $N - 1$ 行描述藤蔓。每行包含两个不同的整数 $u$ ($1 \le u \le N$) 和 $v$ ($1 \le v \le N$)，表示花朵 $u$ 和 $v$ 之间有一条藤蔓。

输出格式

输出你能派遣去执行任务的蜂群所能提供的最大授粉能力总和。

样例

样例输入 1

5 10
2 1
2 2
2 4
2 8
2 16
1 2
2 3
3 4
4 5

样例输出 1

21

样例输入 2

7 10
1 7
2 4
5 18
2 3
3 12
9 20
2 8
1 2
1 3
2 4
2 5
3 6
3 7

样例输出 2

33