Description

有 n 小球，要求把这 n 个球放到到一棵树上。

这棵树有 n 个节点，每个节点有两个值 ai,bi，每放一个球在节点 i ，就会得到一定的美丽值,如果在节点 i 放了球之后已经放有球节点集合为 S ，则可以获得 $$ bi×\sum_{j\notin S}aj $$ 点价值。

一开始只能把球放在树的根节点，并获得 0 点美丽值，随后可以把球放到任何一个点 v 满足 $$ ∃E(u,v),E∈G,u∈V,v∈V,u∈S,v∉S $$，并获得相应的价值。

如何才能获得最大的价值。

Format

Input

第一行一个整数 n(1≤n≤100000) 表示树的节点个数和球个数。

第二行 n−1 个整数，第 i 个整数 fi​ 表示第 i+1 个点的父亲是 fi(1≤fi≤i) 。

接下去 n 行每行 2 个整数 ai,bi(0<ai,bi≤10000) ，表示节点 i 的 a,b 值，保证根节点 a1,b1​ 均为 0 。

Output

一行一个整数表示最大价值。

Samples

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

14

Limitation

1s, 1024KiB for each test case.