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

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

你的朋友想知道，在满足上述限制的情况下，树上装饰品的总重量最大可能是多少。你能帮他们算出来吗？

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$ ($1 \le N \le 2 \cdot 10^5, 0 \le K \le 10^9$)，分别表示树的节点数和重量常数。

下一行包含 $N$ 个空格分隔的整数。第 $i$ 个整数（从 $i=1$ 开始）要么是 $-1$，要么是一个非负整数。如果它是 $-1$，你可以为节点 $i$ 自由选择任何装饰品。如果它是一个非负整数 $w_i$ ($0 \le w_i \le 10^9$)，则你的朋友坚持要求你在节点 $i$ 上放置一个重量为 $w_i$ 的装饰品。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$ ($1 \le a, b \le N$)，表示节点 $a$ 和 $b$ 之间有一条边。输入图保证是一棵树：图中任意一对节点之间都存在唯一的路径。

输出格式

如果无法以满足上述所有限制的方式在树上放置装饰品，请输出 $-1$。否则，输出在满足限制的前提下，树上装饰品的总重量最大值。

样例

样例输入 1

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

样例输出 1

18

样例输入 2

1 5
-1

样例输出 2

5

样例输入 3

2 5
5 5
1 2

样例输出 3

-1