Problem Description

• There is a rooted tree with $n$ vertices, with root $1$. Vertex $i$ contains $c_i$ items, each having value $v_i$.
• First, you need to choose $t$ distinct vertices. For every chosen vertex, take one item from each of its ancestors (including itself).
  • It is guaranteed that $\boldsymbol{t < c_i}$, so there will never be a case where there is no item to take.
• Next, you may take at most $k$ items. All vertices from which items are taken in this step must form a connected subgraph that contains the root.
• Maximize the total value of all items taken during the whole process.

Input Format

• The first line contains three integers $n, k, t$.
• The next $n$ lines each contain two positive integers, representing $c_i$ and $v_i$.
• The last line contains $n - 1$ positive integers. The $i$-th integer denotes the parent $\mathrm{fa}_{i+1}$ of vertex $(i + 1)$ in the tree.

Output Format

• Output one line containing a non-negative integer: the maximum possible sum of values.

Example

Example 1 Input

4 4 1
2 1 
2 1
2 5
2 1
1 1 2

Example 1 Output

15

Constraints

For all data: $1 \leq n, k \leq 10^4$, $0 \leq t \leq n$, $\boldsymbol{t < c_i} \leq 10^9$, $1 \leq v_i \leq 10^9$, $\mathrm{fa}_i < i$, $nk(t+1) \leq 10^7$.

Scoring

• Subtask 1 (10 points): $n, k, t \leq 10$.
• Subtask 2 (20 points): $t = 0$.
• Subtask 3 (15 points): $nk(t + 1) \leq 10^6$.
• Subtask 4 (25 points): $nk(t + 1) \leq 5 \times 10^6$.
• Subtask 5 (30 points): No special constraints.