Хаймарс-2

Обмеження: 3 сек., 256 МіБ

У корені (вершині 1) зваженого дерева з \(n\) вершин знаходитьcя Хаймарс з радіусом пострілу \(r\). Якщо Хаймарс знаходиться у вершині \(u\), то він може атакувати вершину \(v\), якщо відстань від вершини \(u\) до вершини \(v\) не більше \(r\). У деяких вершинах (не у корені) дерева знаходиться русня. Вершини, у яких є або була русня, заміновані і заїжджати в них заборонено. Хаймарс може вільно проїжджати по ребрах між вершинами, які не заміновані. Потрібно знайти множину вершин мінімального розміру, стріляючи з яких можна знищити всю русню, та у всі ці вершини може заїхати Хаймарс.

Вхідні дані

У першому рядку задано два цілих числа — \(n\) та \(r\).

У наступному рядку задано задано \(n\) цілих чисел \(a_i\) — \(a_i\) рівне 1, якщо у вершині \(i\) знаходиться русня, або 0 у іншому разі.

У кожному з наступних \(n - 1\) рядків задано по три цілих числа, які описують ребра дерева: \(u_i\), \(v_i\) та \(l_i\) — номери вершин, які з’єднує \(i\)-те ребро дерева та його довжина.

Вихідні дані

Виведіть одне ціле число — мінімальний розмір множини вершин, стріляючи з яких можна знищити всю русню.

Якщо без розмінування вершин всю русню знищити не вдасться, виведіть Demining is required..

Обмеження

\(1 \le n \le 5 \cdot 10^5\),

\(1 \le u_i, v_i \le n\), \(u_i \ne v_i\),

\(1 \le l_i \le r \le 10^9\),

\(0 \le a_i \le 1\),

\(a_1 = 0\).

Приклади