Description

Xiao A fell in love with Xiao B!!! However, Xiao A is too weak compared to Xiao B, so she would certainly not agree to Xiao A’s request. After Xiao A’s persistent pursuit, Xiao B set the following conditions:

• Xiao B has $n$ subordinates (excluding Xiao B) forming a tree structure. Xiao B is at the top, and everyone else has exactly one direct superior.
• Xiao B is numbered $0$, and others are numbered $1 \sim n$.
• For the $i$-th person: if this person has no subordinates, then Xiao A can give them $A_i$ yuan, after which they will write a letter to their direct superior, stating that Xiao A is confessing to Xiao B.
• If at least a proportion of $\dfrac{A_i}{T}$ among their direct subordinates write letters stating that Xiao A is confessing to Xiao B, then they will also write a letter to their direct superior.
• If at least a proportion of $\dfrac{C}{T}$ among Xiao B’s direct subordinates write letters stating that Xiao A is confessing to Xiao B, then she will agree to Xiao A’s request.

Please determine the minimal total amount of money Xiao A needs to pay to make Xiao B accept Xiao A’s confession.

Input Format

The first line contains three integers $n, T, C$.

Then follow $n$ lines. The $i$-th line contains two integers $B_i, A_i$, where $B_i$ is the direct superior of $i$, and it is guaranteed that $B_i < i$.

Output Format

Output the minimal total amount of money needed.

14 5 3
0 3
0 3
1 10
1 10
2 3
2 10
2 3
5 10
7 10
5 10
7 10
5 10
7 10
5 10

50

Hint

• For $20\%$ of the testdata, the number of people without direct subordinates $\le 15$.
• For $40\%$ of the testdata, $n \le 2000$.
• Additionally, for $10\%$ of the testdata, $B_i = 0$.
• Additionally, for $10\%$ of the testdata, $C = 1$ and for people with direct subordinates $T / A_i > n$.
• Additionally, for $10\%$ of the testdata, $B_i = i - 1$.
• For $100\%$ of the testdata, $1 \le n \le 500000$, $1 \le T \le {10}^9$, $B_i < i$, $1 \le A_i \le T$.

Translated by ChatGPT 5