在某些方面，拜特国（Bajtocja）是一个相当落后的国家：尽管所有邻国早已拥有铁路，但该国至今仍未通铁路。这种情况必须改变！

拜特国国家铁路公司总工程师拜特扎尔（Bajtazar）设计了一个铁路网。该网络连接了拜特国境内的一些车站以及境外的一些车站。每条铁路线路连接两个车站，且是双向的。从网络中的任意一个车站出发，都可以通过唯一的一条路径到达其他任何车站，且路径中不会重复经过任何车站。

不幸的是，情况变得复杂了，因为每个邻国都采用了自己独特的轨距标准。此外，拜特国境外的任何车站都无法更改轨距。因此，工程师拜特扎尔决定：拜特国境内不会有统一的轨距标准——每个拜特国境内的车站都可以有不同的轨距。而在连接车站的铁路上，将建造 BAZRK（拜特自动轮距变换系统），允许火车在行驶过程中改变轮距。

BAZRK 系统显然是一种相当昂贵的解决方案；如果两个相连车站的轨距分别为 $r_1$ 和 $r_2$（单位为比特米），那么在连接它们的轨道上建造 BAZRK 系统的成本为 $|r_1 - r_2|$（单位为兆比特拉）。

请帮助拜特扎尔为拜特国境内的每个车站选择轨距，以使 BAZRK 系统的总成本最小化。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000, 1 \le m \le n$)，分别表示网络中车站的总数（包括拜特国境内和境外）以及境外车站的数量。境外车站编号为 $1$ 到 $m$，境内车站编号为 $m + 1$ 到 $n$。

接下来的 $n - 1$ 行描述了车站之间的铁路连接：第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示编号为 $u_i$ 和 $v_i$ 的车站之间存在直接的铁路连接。每个境外车站恰好与另一个车站相连，每个境内车站至少与另外两个车站相连。

接下来的 $m$ 行包含境外车站的轨距：第 $i$ 行包含一个整数 $r_i$ ($1 \le r_i \le 500\,000$)，表示编号为 $i$ 的境外车站的轨距（单位为比特米）。

输出格式

输出一行，包含安装 BAZRK 系统的最小总成本（单位为兆比特拉），向下取整到最接近的整数。

样例

输入 1

6 4
1 5
2 5
3 6
4 6
5 6
5
10
20
40

输出 1

35