HIMARS-2

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian.

At the root (vertex 1) of a weighted tree with \(n\) vertices, there is a HIMARS with a firing radius \(r\). If the HIMARS is at vertex \(u\), it can attack vertex \(v\) if the distance from vertex \(u\) to vertex \(v\) is at most \(r\). At some vertices (not the root) of the tree, there are russians. Vertices that have or had russians are mined, and driving into them is forbidden. The HIMARS can freely move along edges between vertices that are not mined. You need to find a set of vertices of minimum size, firing from which can destroy all russians, and the HIMARS can drive to all these vertices.

Input

The first line gives two integers — \(n\) and \(r\).

The next line gives \(n\) integers \(a_i\) — \(a_i\) is equal to 1 if there are russians at vertex \(i\), or 0 otherwise.

In each of the following \(n - 1\) lines, three integers are given, describing the edges of the tree: \(u_i\), \(v_i\), and \(l_i\) — the numbers of the vertices connected by the \(i\)-th edge of the tree and its length.

Output

Print a single integer — the minimum size of the set of vertices, firing from which can destroy all russians.

If all russians cannot be destroyed without demining vertices, print Demining is required..

Constraints

\(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\).

Samples