In some respects, Byteotia is a rather backward country: it still has no railways, even though all neighboring countries have had them for a long time. This must change!

Bajtazar, the chief engineer of the newly founded Byteotian State Railways, has designed a railway network. The network connects a certain number of stations in Byteotia and a certain number of stations outside its borders. Each railway connection runs between two stations and is bidirectional. From any station in the network, one can reach any other station in exactly one way, without visiting any station twice.

Unfortunately, the matter is complicated by the fact that each neighboring country has introduced its own rail gauge standard. It is also impossible to change the rail gauge at any station outside the borders of Byteotia. For this reason, engineer Bajtazar has decided the following: there will be no common rail gauge standard for all of Byteotia – the rail gauge at each Byteotian station can be different. However, on the railway connections between stations, BAZRK (Byteotian Automatic Wheel Gauge Changing) systems will be built, allowing the train's wheel gauge to be changed while in motion.

BAZRK systems are, of course, a rather expensive solution; if the rail gauges at two connected stations are $r_1$ and $r_2$ bitometers respectively, then building a BAZRK system on the tracks connecting them costs $|r_1 - r_2|$ megabyte-thalers.

Help Bajtazar choose the rail gauges at each station in Byteotia to minimize the total cost of the BAZRK systems.

Input

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 500\,000$, $1 \le m \le n$), representing the total number of stations (both Byteotian and foreign) in the network and the number of foreign stations, respectively. Foreign stations are numbered from $1$ to $m$, and domestic stations are numbered from $m + 1$ to $n$.

The next $n - 1$ lines describe the network of railway connections between stations: the $i$-th of these lines contains two integers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), indicating that there is a direct railway connection in the network between stations numbered $u_i$ and $v_i$. Each foreign station is connected to exactly one other station, and each domestic station is connected to at least two other stations.

The next $m$ lines contain the rail gauges at the foreign stations: the $i$-th of these lines contains an integer $r_i$ ($1 \le r_i \le 500\,000$) representing the rail gauge (in bitometers) at foreign station number $i$.

Output

The only line of output should contain the minimum possible total cost of the installed BAZRK systems in megabyte-thalers, rounded down to the nearest integer.

Examples

Input 1

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

Output 1

35