P6079 [USACO06MAR] Milk Team Select G

Farmer John’s $N(1 \le N \le 500)$ cows plan to take part in a world-class milking contest (Multistate Milking Match-up, MMM), and they have already figured out how strong the other teams are. As long as their total milk production is at least $X$ gallons ($1 \leq X \leq 10^6$), they can win. Each cow can contribute some amount of milk to the team, ranging from $-10^4$ to $10^4$ gallons (why negative? because some cows may spill the milk produced by other cows). The goal of MMM is to improve teamwork among family members through cooperation. To support the spirit of the contest, the cows want, while still winning the contest, to have as many pairs of cows as possible that are in a direct blood relationship. Of course, all cows are female, so the direct blood relationship here means a mother-daughter relationship. Now FJ knows all the family relationships among the cows, and wants to compute, under the condition that the team can win, what is the maximum number of related pairs that can exist within a team. Note: if a team consists of a cow, her mother, and her grandmother, then this team has only two related pairs (the cow and her mother, and the mother and the grandmother).

The first line contains two integers $N, X$. The next $N$ lines each contain two integers. The first integer is the amount of milk she can contribute to the team, and the second integer is her mother’s index; if her mother is not in the herd, this number is $0$. It is guaranteed that the family relationships contain no cycles.

Output the maximum number of family relationships that can exist in a team, under the condition that the team wins. In particular, if there is no team that can win, output $-1$.

The best team contains cows $1, 2, 3, 5$. The total milk production is $9$ gallons, and there are two related pairs ($1, 2$ and $1, 3$). Although the combination $2, 3, 5$ produces more milk, there are no family relationships in that combination. Translated by ChatGPT 5