Roger was having fun solving his problems until he found this one. As you know, an undirected connected graph with N nodes and N-1 edges is called a tree. You are given an integer 'K' and a tree consisting of 'N' nodes. Each node 'i' has a value a(i) associated with it.

We call a path 'P' of tree valid if following conditions are satisfied:

• P has at least 2 nodes associated with it.
• Max a(u) - Min a(u) >= K (u belongs to the nodes present in the chosen P).

Your task is to count the number of Valid Paths.

Input

The first line contains two space-separated integers N and K.

The second line contains N space-separated positive integers a(1), a(2) ... a(n).

Then the next n - 1 line each contains a pair of integers u and v denoting that there is an edge between u and v.

Output

Print the number of Valid Paths.

Example

Input:
3 1
1 2 3
1 2
2 3

Output:
3

Constraints

1 ≤ N ≤ 5000
1 ≤ u, v ≤ N
0 ≤ K ≤ 10⁹
0 ≤  ai ≤ 10⁹

Like trees? Try the problems: RTREE and RTREE3 too.