Description

有一个N个结点的有根树，R是这个树的根。

现在要对这N个结点依次进行染色，每个结点染色要花费1个单位的时候，

同时要满足一个结点仅在其父亲被染色后才可被染色，每个结点有个权值Ci,

如果我们在第Ti时间对i号结点染色，则付出总代价为Sigma(Ti*Ci),1<=i<=N.

现在给出这个树和每个点的权值，请构造一种染色顺序，使得总代价最小.

N<=1000

Format

Input

第一行正整数N.R

第二个给出N个数字，代表每个点的权值ci

接下来N-1描述这个树

Output

最小的总代价

Samples

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

33

Hint

先染1号点，代价为1 * 1 =1

再染2号点，代价为2 * 3 = 6

再染4号点，代价为3 * 6 =18

再染3号点，代价为4 * 2 =8

总代价为33