You are given a tree with n nodes, where the i-th node has an assigned value (). Your task is to find the number of paths in the tree that start from the root node and have a sum equal to a given value s.

Input

The first line contains two integers separated by a space: n and s (), representing the number of nodes in the tree and the target sum respectively.
The second line contains n space-separated integers through (), representing the values assigned to each node in the tree.
The following n-1 lines represent the edges of the tree, with each line containing two space-separated integers a and b (1 β€ a, b β€ n), indicating an edge between nodes a and b. It is guaranteed that the given edges form a tree.

Output

Print a single integer, representing the number of paths in the tree that start from the root node and have a sum equal to the given value s.