Description

有这样一个神奇的国家，有 $n$ 座城市，编号为 $1$ 到 $n$。

城市之间由 $n-1$ 条公路相连，保证任意城市出发可以到达其他的所有城市。

在每个城市中都有一个宝物，节点 $i$ 上的宝物价值为 $w_i$。

你正在计划一场旅行，你可以选择从这个国家的任意一座城市开始，将你经过的城市中的宝物收集起来，直到总价值恰好为 $k$ 时并离开，但一个城市只能进入一次。

你想知道有多少种路线可以满足你的计划。

Format

Input

一行输入两个整数 $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^9$)，分别表示城市的数量和你期望的总价值。

一行输入 $n$ 个整数 $w_i$ ($1 \le w_i \le 10^5$)，表示每座城市中宝物的价值。

$n - 1$ 行每行输入两个整数 $u, v$ ($1 \le u, v \le n$)，表示有一条连接城市 $u$ 和城市 $v$ 的公路。

题目保证输入的 $n-1$ 条公路一定使 $n$ 座城市联通。

Output

一行输出一个整数，表示不同的路线数量。

注意，路线是有向的，$[1,3,4]$ 与 $[4,3,1]$ 是不同的路线。

Samples

7 3
1 1 2 1 2 1 2
1 2
1 3
2 4
2 5
3 6
3 7

8

7 4
1 1 2 1 2 1 2
1 2
1 3
2 4
2 5
3 6
3 7

10

7 8
1 1 2 1 2 1 2
1 2
1 3
2 4
2 5
3 6
3 7

2

Hint

在第三个样例中，只有 $[5-2-1-3-7]$ 与 $[7-3-1-2-5]$ 满足要求。