给定一个包含 $n$ 个节点的计算机网络。该网络构成一棵无向树。第 $i$ 条边连接节点 $a_i$ 和节点 $b_i$，其距离为 $c_i$。每个节点都有不同的数据，第 $i$ 个节点上的数据大小为 $s_i$。网络用户可以将任何数据从任意节点传输到任意节点。传输成本定义为用户传输的数据大小与从源节点到目标节点距离的乘积。数据通过传输路径上的最短路径进行传输。每个节点都会进行缓存以减少网络负载。在每次传输中，传输的数据会被缓存到所有中继该数据的节点（包括目标节点）。从下一次传输开始，数据可以从任何已缓存该数据的节点进行传输。因此，传输成本减少为原始数据大小与最近的已缓存节点到目标节点之间距离的乘积。

计算在给定网络上进行 $m$ 次后续传输的最大成本。所有节点在开始时都没有缓存数据。用户可以任意选择每次传输的源节点和目标节点。

输入格式

输入包含单个测试用例。第一行包含两个整数 $n$ ($2 \le n \le 2000$) 和 $m$ ($1 \le m \le 10^9$)。$n$ 和 $m$ 分别表示网络中的节点数和传输次数。接下来的 $n-1$ 行描述了网络结构。其中第 $i$ 行包含三个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$) 和 $c_i$ ($1 \le c_i \le 10^4$)，表示第 $a_i$ 个节点和第 $b_i$ 个节点之间连接有一条距离为 $c_i$ 的边。下一行包含 $n$ 个整数。第 $j$ 个整数表示 $s_j$ ($1 \le s_j \le 10^4$)，即第 $j$ 个节点的数据大小。保证给定的网络是一棵树。

输出格式

输出一行，包含在给定网络中进行 $m$ 次后续传输的最大成本。

样例

输入 1

3 2
1 2 1
2 3 2
1 10 100

输出 1

320

输入 2

2 100
1 2 1
1 1

输出 2

2