小z有一棵 n 个点的树，每个点有个点权 $V_i$。小z可以选择一些不相交的路径去覆盖一些点，如果他覆盖了权值和为 S 的点，共用了 K 条路径，则最终收获就是 $\frac{S}{K+1}$。

贪婪的小z为了收获更多会在一开始修改点权，他可以选择一个 0 到 T 中间的整数 C，所有点的点权都会加上 C，不过，所有点的点权都会对一个整数 Limit 取模，即变成 $(V_i+C) \pmod{Limit}$。小z想知道他最大的收获是多少。

输入格式

第一行两个整数 n 和 Limit。

接下来一行 n 个整数 $V_i$。

接下来 n-1 行，每行两个整数 $u_i,v_i$，表示这棵树。

最后一行一个整数 $T$，表示修改范围。

输出格式

一行一个实数，表示答案，当你的答案与标准答案绝对误差不超过 $10{-6}$ 可以获得满分。

样例数据

输入样例一

4 100
1 1 1 1
1 2
1 3
1 4
0

输出样例一

1.5

数据规模与约定

本题采用捆绑测试

对于 15 分的数据，$n \le 2000,T=0$；

对于另外 15 分的数据，$n \le 2000,Limit \le 100$；

对于另外 30 分的数据，$n\le 1000$

对于所有的数据， $n\le 5000,V_i,T < Limit \le 10^6$。

时间限制：$1\text{s}$

空间限制：$512\text{MB}$