题目描述

你正在帮朋友装饰圣诞树！有趣的是，圣诞树上挂装饰品的位置可以用一棵（图论中的）树来表示，树的节点编号为 $1$ 到 $N$，其中节点 $1$ 是树的根，其他节点编号任意。你有无限多个重量为非负整数（包括 $0$）的装饰品，必须在树的每个节点上恰好挂一个装饰品。

不过，朋友对装饰方式有一些限制。首先，他们对某些节点必须挂什么装饰品有严格要求；你只能自由选择其他节点的装饰品。其次，圣诞树的每个区域只能承受一定重量：如果一个节点及其所有直接子节点上的装饰品重量之和超过常数 $K$，整棵树就会倒塌！

在满足上述限制的条件下，朋友想知道树上装饰品的最大可能总重量。你能帮他们找到答案吗？

输入格式

第一行输入两个整数 $N$ 和 $K$（$1 \leq N \leq 2 \cdot 10^5$，$0 \leq K \leq 10^9$），分别表示树的节点数量和重量限制常数。

第二行包含 $N$ 个整数。第 $i$ 个整数（从 $i=1$ 开始）为 $-1$ 或一个非负整数。如果是 $-1$，你可以自由选择节点 $i$ 的装饰品；如果是非负整数 $w_i$（$0 \leq w_i \leq 10^9$），则朋友要求你必须将重量为 $w_i$ 的装饰品挂在节点 $i$ 上。

接下来 $N-1$ 行每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq N$），表示节点 $a$ 和 $b$ 之间有一条边相连。输入保证是一棵树：图中任意两个节点之间有且仅有一条路径。

输出格式

如果无法在满足所有限制条件的情况下装饰圣诞树，输出 $-1$。否则，输出在限制条件下树上装饰品的最大可能总重量。

输入输出样例 #1

输入 #1

5 10
-1 2 3 -1 -1
1 2
1 3
2 4
2 5

输出 #1

18

输入输出样例 #2

输入 #2

1 5
-1

输出 #2

5

输入输出样例 #3

输入 #3

2 5
5 5
1 2

输出 #3

-1