暂无测试数据。

在上古时代，有一个简单的树上游戏。能通关这个游戏的幸运签到者，将会收到一份小礼包。

树上游戏是这样的：

出题人会给挑战者一棵 $n$ 个结点的有根树，每个结点从 $1$ 到 $n$ 编号，有根树的根为 $1$ 号结点。

有根树的每个结点有权值，第 $i$ 个结点的权值为 $w_i$。对于有根树的每个结点，可以定义其深度为该结点到根结点路径上的结点数，第 $i$ 个结点的深度为 $d_i$。

挑战者需要完成的任务是：在有根树上选择一些结点，在满足下述条件的情况下，最大化选择结点的权值和：

• 我们称两个被选择的结点是联通的，当且仅当存在一条以这两个结点为端点的路径，路径上每个点都被选择。
• 对于任意两个联通的点，我们称其属于同一个联通块。
• 对于一个联通块，我们要求联通块内任意两个结点之间的深度差的绝对值，不大于给定参数 $k$。

作为挑战者，你需要在最快时间内完成这个任务。

输入格式

第一行，两个正整数 $n,k$，表示有根树的结点数，给定的参数。

第二行，$n$ 个正整数 $w_1,\cdots,w_n$，表示每个结点的权值。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边连接的两个结点的编号。

输出格式

输出一行一个整数，表示你的答案，即选择结点的权值和的最大值。

数据范围

对于所有数据，保证有 $1\leq n\leq 10^6$，$0\leq k\leq n$，$1\leq u,v\leq n$，$0\leq w_i\leq 10^9$。

子任务 1（$10\%$）：$1\leq n\leq 1000$，$0\leq k\leq 1000$。

子任务 2（$10\%$）：$1\leq n\leq 10^5$，$k=0$。

子任务 3（$10\%$）：$1\leq n\leq 10^5$，$0\leq k\leq 1$。

子任务 4（$30\%$）：$1\leq n\leq 10^5$，$0\leq k\leq 10^5$，有根树随机生成。

子任务 5（$40\%$）：$1\leq n\leq 10^6$，$0\leq k\leq 10^6$。

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

42

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

44