Winning the Milking Match-up

Farmer John's N cows (where \(1 \le N \le 500\)) plan to enter the Multistate Milking Match-up (MMM). They know that if their total milk production is at least \(X\) gallons (\(1 \le X \le 10^6\)), they win the contest. Each cow contributes a certain amount of milk – a value between \(-10^4\) and \(10^4\); note that some cows may contribute negatively (they might spill milk produced by other cows).

Furthermore, the cows have direct maternal relationships (i.e. mother-daughter relationships). In a team, for every pair of cow and her mother that are both selected, the team gains 1 kinship point. Note: If a team includes a cow, her mother, and her grandmother, there are only 2 kinship pairs (cow-mother and mother-grandmother).

Your task is to choose a subset of cows (possibly from a forest of trees defined by the maternal relationships) such that the total milk production is at least \(X\) and the number of direct mother-daughter pairs (i.e. kinship pairs) among the chosen cows is maximized. If it is impossible to achieve total milk production \(\ge X\), output -1.

The input provides the number of cows \(N\) and the target milk production \(X\), followed by a list of milk production values for each cow and a list of integers indicating the mother of each cow (with 0 meaning the cow has no mother).

Input Format Example:

N X
a[1] a[2] ... a[N]
m[1] m[2] ... m[N]

Here, \(a[i]\) is the milk production of cow \(i\) (which can be negative) and \(m[i]\) is the index of cow \(i\)'s mother (0 if none).

inputFormat

The first line contains two integers \(N\) and \(X\). \(N\) is the number of cows and \(X\) the minimum required milk production.

The second line contains \(N\) integers \(a[1], a[2], \ldots, a[N]\) representing the milk production (in gallons) of each cow.

The third line contains \(N\) integers \(m[1], m[2], \ldots, m[N]\) where \(m[i]\) is the index of cow \(i\)'s mother (or 0 if cow \(i\) has no mother).

outputFormat

Output a single integer: the maximum number of mother‐daughter (direct kinship) pairs in a team whose total milk production is at least \(X\). If no such team exists, output -1.

sample

3 10
5 6 -1
0 1 1

1