您有一个由 n 个顶点组成的加权树。每个顶点要么涂成黑色,要么涂成红色。一棵红黑树被称为美丽的,如果对于它的任何顶点我们可以在距离不超过 x 处找到一个黑色顶点。
两个节点之间的距离是它们之间的最短路径。
你有一棵红黑树。你的任务是用最少的颜色交换操作让它变得漂亮。在一个颜色交换操作中,您可以选择不同颜色的两个顶点并将它们分别绘制为另一种颜色。换句话说,如果您选择红色顶点 p 和黑色顶点 q,则在一次操作中您可以将 p 涂成黑色,将 q 涂成红色。
打印所需操作的最少数量。
输入
第一行包含两个整数 n 和 x (2 ≤ n ≤ 500; 1 ≤ x ≤ 109)。下一行包含 n 个整数,每个整数不是零就是一。如果第 i 个数等于 1,则树的顶点 i 为黑色,否则顶点 i 为红色。接下来的 n - 1 行包含树的边缘。第 j 行包含整数 uj vj wj (1 ≤ uj, vj ≤ n; uj ≠ vj; 1 ≤ wj ≤ 109),这意味着树在顶点 vj 和 uj 之间有一条权重为 wj 的边。
假设树顶点编号为 1 到 n。
输出
打印单个整数 — 所需交换操作的最小数量。
如果通过任意次数的操作都不可能得到一棵美丽的树,则打印 -1。
示例
输入 #1
3 2 1 0 0 1 2 2 2 3 2
输出 #1
1
输入 #2
4 2 0 1 0 0 1 2 2 2 3 2 3 4 2
输出 #2
-1