Algorithms and Data Structures

Path Sum From Root

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.

Examples

Input
Output
5 6 1 2 3 4 5 1 2 2 3 1 5 5 4
2

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue