Spring Equinox Tree Decorations

Farmer John is decorating his Spring Equinox Tree – a rooted tree with N nodes numbered 1…N (where 1 is the root). For each node i we are given two numbers:

• C_i – the minimum number of ornaments that must appear in the subtree rooted at node i (0 ≤ C_i ≤ 10 7).
• T_i – the time required to place one ornament at node i (1 ≤ T_i ≤ 100).

Every node (except the root) has a parent given by P_i (1 ≤ P_i ≤ N). The root’s parent is indicated by –1.

An ornament placed at any node counts toward the ornament total of every ancestor (including the node itself). Farmer John may place ornaments arbitrarily at the nodes; if he places K ornaments at node i his time cost increases by K·T_i. His goal is to satisfy the constraint that for every node i the total number of ornaments in its subtree is at least C_i, while minimizing the total time cost.

One may think of the problem as buying ornaments from different nodes. An ornament placed at node i costs T_i time units, but because an ornament is “shared” by all ancestors, if a child node has a lower T-value than its parent then its ornaments are preferable to meeting an ancestor’s quota. In other words, if extra ornaments are needed toward satisfying an ancestor’s requirement, it is best to “source” them from the descendant with the lowest cost among those available in the subtree.

The optimal strategy can be computed by a DFS that “merges” the supplies from the subtrees. Let each node i have an optimal supply quantity S_i (the total number of ornaments available in the subtree) and an associated cost COST_i which is the minimum time needed to achieve that supply. If the children can supply a total of X ornaments (at an effective marginal cost equal to the minimum among the children) then node i may choose to add extra ornaments at its own cost T_i (or, if available, at the better rate coming from below) so that S_i = max( C_i, X ). In the end the answer is the minimum total time computed at the root. (It is guaranteed that the answer fits into a signed 64‐bit integer.)

Example

For example, consider a tree of 5 nodes. The parent array (with node 1 being the root) is:
  Node:    1   2   3   4   5
  Parent: -1   1   5   5   2

The subtree constraints and installation times are:

            C[i]    T[i]
         ----------------
         1:  9      3
         2:  2      2
         3:  3      2
         4:  1      4
         5:  3      3

One optimal solution is to place ornaments as follows (note that an ornament placed at a node counts in the subtree of every ancestor):

   Node 3: place 5 ornaments (cost = 5×2 = 10).
   Node 4: place 1 ornament  (cost = 1×4 = 4).
   Node 2: place 3 ornaments (cost = 3×2 = 6).
   Node 1 and 5: no ornaments are placed.

Then the total ornaments in each subtree are:
  - Subtree 3: 5 ≥ 3
  - Subtree 4: 1 ≥ 1
  - Subtree 5: 5+1 = 6 ≥ 3
  - Subtree 2: 3+6 = 9 ≥ 2
  - Subtree 1: 9 ≥ 9

Total cost = 10 + 4 + 6 = 20, which is optimal.

inputFormat

The input begins with a line containing a single integer N (1 ≤ N ≤ 100,000), the number of nodes in the tree.

The next line contains N space‐separated integers. The i^th integer is the parent of node i (for the root, node 1, the parent is given as –1).

Then follow N lines; the i^th of these lines contains two space‐separated integers: C_i and T_i, the minimum number of ornaments required in the subtree of node i and the time cost per ornament at node i respectively.

It is guaranteed that 0 ≤ C_i ≤ 10,000,000 and 1 ≤ T_i ≤ 100.

outputFormat

Output a single integer, which is the minimum total time required to decorate the tree so that every subtree’s ornament count is at least its required minimum.

Note: The answer fits into a signed 64‐bit integer.

sample

5
-1 1 5 5 2
9 3
2 2
3 2
1 4
3 3

20