一位商人想要通过在城市间旅行并进行货物贸易来赚取利润。共有 $N$ 座城市，编号为 $1, \dots, N$，以及 $N-1$ 条道路。每条道路连接两座城市，通行需要一天。通过这些道路，可以从任意城市到达其他任何城市。

如果商人当前位于第 $i$ 座城市并选择在该城市进行贸易，则可以获得 $p_i$ 的利润，但该利润只能获得一次。商人从在城市 $1$ 进行贸易开始，并希望沿着道路在城市间旅行，以最大化总利润。然而，如果商人连续超过 $K$ 天没有增加总利润，老板就会不高兴并解雇商人。注意，无论商人是否在城市中进行贸易，在相邻城市间移动都需要一天。我们希望求出商人在此条件下能获得的最大利润，以及实现该利润的一条路线。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)，描述一条道路。

最后一行包含 $N$ 个整数 $p_1, \dots, p_N$ ($1 \le p_i \le 10^9$)，表示在对应城市进行贸易所获得的利润。

输出格式

第一行输出可能的最大总利润。

第二行输出 $M$ ($1 \le M \le N$)，即商人在最优路线中进行贸易的城市数量。

第三行输出 $M$ 个空格分隔的整数 $x_1, \dots, x_M$，表示商人在最优路线中进行贸易的城市顺序，起始必须为 $x_1 = 1$。

如果存在多个可能的正确输出，接受任意一个即可。

样例

输入 1

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

输出 1

7
2
1 3

说明 1

第 1 天，商人在城市 1 开始贸易，获得利润 3。

第 2 天，商人移动到城市 3 并进行贸易，获得利润 4。

此时，商人在被解雇前无法到达另一个尚未进行过贸易的城市，因此总利润为 7。

输入 2

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

输出 2

14
5
1 4 5 2 3

说明 2

商人可以通过按 1, 2, 4, 2, 5, 2, 1, 3 的顺序访问城市，从而在每座城市都获得利润。

注意，商人策略性地推迟了在城市 2 进行贸易的时间，以确保他们不会连续超过 2 天没有获得利润。