给定一棵包含 $n$ 个顶点的树。每个顶点 $i$ 都有一个权重 $a_i$。

你需要从任意一个顶点出发遍历整棵树，沿着边移动，使得每条边在每个方向上都被恰好遍历一次（换句话说，你执行一次深度优先搜索遍历，初始顶点和每一步选择外出边的顺序均可任意指定）。记下所有顶点首次被访问到的顺序，记为 $(v_1, v_2, \dots, v_n)$。你将获得 $\sum_{i=1}^{n} i \cdot a_{v_i}$ 的惩罚值。

你的目标是最小化该惩罚值。注意 $(v_1, v_2, \dots, v_n)$ 是 $(1, 2, \dots, n)$ 的一个排列，$v_1$ 是你开始遍历的顶点。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示顶点的数量。接下来的 $n-1$ 行包含边的描述：第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示连接 $u_i$ 和 $v_i$ 的边。第三行包含 $n$ 个空格分隔的整数 $a_i$ ($1 \le a_i \le 200\,000$)。

保证给定的边构成一棵树。

输出格式

输出一行，包含一个整数，表示最小可能的惩罚值。

样例

样例输入 1

3
1 2
1 3
1 2 3

样例输出 1

11

样例输入 2

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

样例输出 2

35