给定一棵二叉树。深度最大的节点位于整棵树的最深一层，这些节点一定都是叶子节点。

请先确定二叉树的最大深度，再求出所有位于这一深度的叶子节点值之和。

输入格式

第一行一个整数 $n$，表示二叉树的节点数。节点编号为 $1$ 到 $n$，根节点编号为 $1$；当 $n=0$ 时表示空树。

当 $n>0$ 时，第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示节点 $i$ 保存的值。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子编号和右孩子编号。编号 $0$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

输出格式

输出一个整数，表示最深一层全部叶子节点的值之和。

5
42 5 25 47 71
2 0
0 3
4 5
0 0
0 0

118

2
52 32
0 2
0 0

32

4
28 61 61 65
2 0
0 3
0 4
0 0

65

数据范围与约定

• 树中节点数目在范围 [1, $10^4$ ] 之间
• 1 ≤ v_i ≤ 100