#3935. Rbtree

内存限制:512 MiB 时间限制:100 Sec

题目描述

给定一颗 N 个点的树,树上的每个点或者是红色,或者是黑色。
每个单位时间内,你可以任选两个点,交换它们的颜色。
出于某种恶趣味,你希望用最少的时间调整结点的颜色,使得对于每个点,离它最近的黑色点与它的距离不超过 x。

输入格式

输入的第一行包含整数 N 和 x(1 <= x <= 10^9)。
接下来一行 N 个整数 C1-Cn,表示结点的初始颜色。1 表示黑色,0 表示红色。
接下来 N-1 行,每行 3 个整数 ui, vi,wi(1 <= wi <= 10^9),表示点 ui 和 vi 之间存在权值为 wi的边。

输出格式

输出一个数表示答案;如果无解,输出 “-1”。

样例

样例输入


			
3 2
1 0 0
1 2 2
2 3 2

样例输出


			
1

数据范围与提示

数据规模和约定

对于100%的数据 N<=500