题目内容

云小核正在玩爆破小游戏，游戏提供了一张地图，可以看成一棵树，地图上有很多节点，每个节点都有被爆破后的收益值，有些节点之间有边和距离。云小核手中有一颗炸弹，可以放置在任意一个节点上。这颗炸弹标定了影响范围，只要和放置炸弹节点的距离（路径上边的和）小于等于影响范围的节点，都会被爆破，云小核获得的收益值是所有被爆破节点收益值的总和。请你帮云小核选择一个炸弹放置点，使得云小核获得的收益最大。

如下图所示，当炸弹放置在节点$2$或节点$3$时，获得收益最大，为 $500$。

输入描述

• 第 $1$ 行：两个整型数值，$N$ 和 $K$，$1 \le N \le 100$ 表示节点数量，$1 \le K \le 100000000$ 表示炸弹影响范围
• 第 $2$ 行：$N$ 个整型数值，$g_1,g_2,…g_N$，$0 \le g_i \le 100000$，表示每个节点对应的收益
• 接下来 $N-1$ 行：三个整型数值，$n_i,n_j,d_k$，$0 \le n_i,n_j \le N-1$，$0 \le d_k \le 100000$，表示节点和节点之间有条边，距离为 $d_k$

输出描述

一个整型数值，表示获得的最大收益

样例1

输入

7 3
10 10 10 300 10 10 300
0 1 1
0 2 1
1 3 3
1 4 1
2 5 3
2 6 1

输出

640

说明

样例2

输入

5 2
200 100 250 100 100
1 0 20
0 2 20
3 1 2
4 1 2

输出

300

说明