E. Красно-черное дерево
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано взвешенное дерево, состоящее из 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 ≤ nuj ≠ vj; 1 ≤ wj ≤ 109), которые обозначают, что в дереве есть ребро веса wj между вершинами vj и uj.

Считайте вершины дерева пронумерованными от 1 до n.

Выходные данные

Выведите единственное целое число — минимальное количество требуемых операций обмена.

Если получить красивое дерево невозможно ни за какое количество операций, выведите -1.

Примеры
Входные данные
3 2
1 0 0
1 2 2
2 3 2
Выходные данные
1
Входные данные
4 2
0 1 0 0
1 2 2
2 3 2
3 4 2
Выходные данные
-1