Problem Description

A merchant wants to conduct business between cities, transporting goods from one city to another to make a profit. There are $N$ cities, denoted as $1, \ldots, N$. There are $N-1$ roads, each connecting two cities, and each road takes one day to traverse. Using these roads, one can travel from any city to any other city.

If the merchant is currently in city $i$ and chooses to conduct business, the merchant can earn a profit of $p_{i}$, but this profit can only be earned once per city. The merchant starts doing business in city $1$, travels along the roads to visit cities, and aims to maximize their total profit. However, if the merchant goes too long without earning a profit, the merchant's boss will become unhappy. Specifically, once the merchant goes more than $K$ consecutive days without earning a profit, the boss will fire the merchant. Note: Regardless of whether the merchant conducts business in one of the cities, moving between adjacent cities takes one day. You need to determine the maximum profit the merchant can earn and construct a route that achieves this profit.

Determine the possible maximum total profit the merchant can earn and construct a scheme.

Input Format

The first line contains two space-separated integers $N$ and $K$.

The next $N-1$ lines each contain two space-separated integers $u_{i}$ and $v_{i}$, representing a road.

The last line contains $N$ integers $p_{1}, \ldots, p_{N}$, representing the profit given for conducting business in the corresponding city.

Output Format

The first line should output an integer, representing the possible maximum total profit.

The second line should output an integer $M\ (1 \leq M \leq N)$, representing the number of cities where the merchant conducts business on the optimal route.

The third line should output $M$ space-separated integers $x_{1}, \ldots, x_{M}$, representing the cities where the merchant conducts business in order on the optimal route, starting with $x_1=1$.

If there are multiple correct schemes, you can output any one.

Sample Input and Output

Sample Input #1

4 1
1 2
1 3
2 4
3 1 4 1

Sample Output #1

7
2
1 3

Sample Input #2

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

Sample Output #2

14
5
1 4 5 2 3

Notes

Sample Explanation 1

On day $1$, the merchant starts in city $1$ and earns a profit of $3$.

On day $2$, the merchant moves to city $3$ and conducts business there, earning a profit of $4$.

On day $3$, the merchant cannot reach another city they haven't done business in before being fired, so their total profit is $7$.

Sample Explanation 2

The merchant visits them in the order $1,2,4,2,5,2,1,3$ and can earn a profit in each city.

Note that the merchant delays conducting business in city $2$ to ensure they do not go more than $2$ days without earning a profit.

For all data, $2 \leq N \leq 2\times 10^5$, $1 \leq K \leq 3$, $1 \leq u_{i}, v_{i} \leq N$, $u_{i} \neq v_{i}$, $1 \leq p_{i} \leq 10^{9}$.

见题面 Input 部分

见题面 Output 部分