暴风雪袭击了长白山的滑雪中心，滑道需要快速清理，才不会影响后续的正常运营。

滑雪中心由 n 条滑道组成。滑道通过总共 n-1 条路径连接，滑道 1 在顶部，从滑道 1 可以通往其他所有滑道。

铲雪机只能沿着路径向下行驶，并且每当铲雪机经过一个滑道时，就会清扫该滑道。由于每个滑道上的积血厚度不一样，那么该滑道需要一定的清扫次数。

君陌通过无人机将铲雪机送到山顶。

问题是，如何通过最少的铲雪机使用次数清扫所有滑道，节约能源？

输入的第一行是一个整数 n，表示滑道的数量。

接下来 n-1 行，每行包含两个整数 a 和 b，表示滑道 a 和滑道 b 之间有一条路径。

最后一行包含 n 个整数 c_1, c_2, \dots, c_n，分别表示滑道 1 到滑道 n 上所需的清扫次数。

输出一个整数：完成清扫，所需的最少铲雪机次数。

提示

样例解释

滑雪中心如下图：

2次沿着路线行驶 (1,2)，3次除雪路线(1,3,4)和1次除雪路线(1,3,5)，累加6次。

数据范围

1 \le n \le 100\,000

0 \le c_i \le 10^9