시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 8 3 3 37.500%

문제

You are given a computer network with n nodes. This network forms an undirected tree graph. The i-th edge connects the ai-th node with the bi-th node and its distance is ci. Every node has different data and the size of the data on the i-th node is si. The network users can deliver any data from any node to any node. Delivery cost is defined as the product of the data size the user deliver and the distance from the source to the destination. Data goes through the shortest path in the delivery. Every node makes cache to reduce the load of this network. In every delivery, delivered data is cached to all nodes which relay the data including the destination node. From the next time of delivery, the data can be delivered from any node with a cache of the data. Thus, delivery cost reduces to the product of the original data size and the distance between the nearest node with a cache and the destination.

Calculate the maximum cost of the m subsequent deliveries on the given network. All the nodes have no cached data at the beginning. Users can choose the source and destination of each delivery arbitrarily.

입력

The input consists of a single test case. The first line contains two integers n (2 ≤ n ≤ 2,000) and m (1 ≤ m ≤ 109). n and m denote the number of the nodes in the network and the number of the deliveries, respectively. The following n − 1 lines describe the network structure. The i-th line of them contains three integers ai, bi (1 ≤ ai, bi ≤ n) and ci (1 ≤ ci ≤ 10,000) in this order, which means the ai-th node and the bi-th node are connected by an edge with the distance ci. The next line contains n integers. The j-th integer denotes sj (1 ≤ sj ≤ 10,000), which means the data size of the j-th node. The given network is guaranteed to be a tree graph.

출력

Display a line containing the maximum cost of the m subsequent deliveries in the given network.

예제 입력

3 2
1 2 1
2 3 2
1 10 100

예제 출력

320

예제 입력 2

2 100
1 2 1
1 1

예제 출력 2

2

힌트