Rick and Morty, on one of their adventures, entered the 4th Dimension and realized that every universe is connected to another universe to form a tree, with the prime universe at the root of that tree.
Along with this, they also discovered that each universe has an evil number assigned to it.
Now, with their splitting gun, they want to split the tree into vertical branches such that the sum of the evil numbers of all these branches is less than some number k.
However, Rick's gun broke while entering the 4th Dimension and now can break the branch with at most m universes. Your task is to split the tree into the minimum number of branches to save the multiverse.
Input Format
n, m, k — the size of the tree, the power of the gun, and the tolerable evilness, respectively.n integers e[i], the evil number of each universe, where 1 ≤ e[i] ≤ 10^9.n-1 integers p[i], where p[i] is the parent of the (i+1)-th universe.Output Format
Output one number: the minimum number of branches. If it is impossible to split the tree, output -1.
Example 1:
Input: n = 6, m = 3, k = 100, e = [1, 100, 1, 1, 1, 1], p = [1, 1, 2, 3, 3]
Output: 4
Explanation:
- Number of universes,
n ≤ 10^5 - The power of the gun,
m ≤ 10^5 - The evilness of each universe and total evilness,
K ≤ 10^18
input:
output: