You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

$MT$ 在摸鱼的时候会偷偷插上手柄玩黑暗之魂！！

题目描述

$MT$ 有 $n$ 点天赋值，他打算把这 $n$ 点天赋点到自己的各项技能点上。

$MT$ 的天赋技能树是一棵奇怪的天赋技能树 $G$ ，这个天赋树有 $n$ 个节点，每个节点有两个值 $a_i$，$b_i$ ，$MT$ 每点一点天赋在节点 ，那么就会得到一定的信仰值，我们假定在节点 $i$，点了天赋之后已经点了天赋的节点集合为 $S$ ，则可以获得 $b_i \times \sum_{j \notin S} a_j$ 点信仰值。

一开始 $MT$ 只能把天赋点在天赋树的根节点，并获得 $0$ 点信仰值，随后 $MT$ 可以把天赋点到任何一个点 $v$ 满足 $\exists E(u,v) \,，\, E \in G, \, u \in V, \, v \in V, \, u \in S, \, v \notin S$，并获得相应的信仰值。

$MT$ 不知道如何才能让信仰值变得最高成为混沌专精，你能帮他吗？

输入

第一行一个整数 $n$$(1 \leq n \leq 100000)$ 表示天赋树的节点个数和总天赋点个数。 第二行 $n - 1$ 个整数，第 $i$ 个整数 $f_i$ 表示第 $i + 1$ 个点的父亲是 $f_i (1 \leq f_i \leq i)$。 接下去 $n$ 行每行 $2$ 个整数 $a_i, b_i (0 < a_i, b_i \leq 10000)$ ，表示节点 $i$ 的 $a,b$ 值，保证根节点 $a_1,b_1$均为 $0$ 。

输出

一行一个整数表示最高信仰值。

样例

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

14

10
1 1 2 2 3 3 6 6 6
0 0
4 1
5000 1
3 1
6 1
200 1
1 1
1 1
1 1
1 1

16040

样例解释

样例解释： 对于第一个样例，我们可以把天赋点数按照这个顺序放 $1−2−4−3$ ，此时信仰值最高。