Description

给一棵n个结点的树，每个结点有一个正整数权值。要求选出一个结点的集合，满足：

1. 这个集合包含1号结点
2. 这个集合在树上是一个连通块。

即，设这个集合为 $S$，则树上存在 $|S|-1$ 条边，这些边连接的结点都属于S。

记一个集合的权值为该集合内所有结点的权值和。

求权值第k小的集合的权值。

Input Format

第一行两个整数n,k。

接下来 n-1 行，每行两个整数u,v，表示结点u和结点v之间有一条边。

接下来一行 n 个整数，表示每个结点的权值。

保证存在权值第k小的集合

对于60%的数据，n<=300000,k<=600000

对于另外40%数据，n<=100000,10^6<=k<=10^18,保证答案不超过500

Output Format

一个整数，表示答案

5 7
1 2
2 3
2 4
4 5
1 2 3 4 5

15