You are given a rooted tree on $n$ vertices, its root is the vertex number $1$. The $i$-th vertex contains a number $w_i$. Split it into the minimum possible number of vertical paths in such a way that each path contains no more than $L$ vertices and the sum of integers $w_i$ on each path does not exceed $S$. Each vertex should belong to exactly one path.

A vertical path is a sequence of vertices $v_1, v_2, \ldots, v_k$ where $v_i$ ($i \ge 2$) is the parent of $v_{i - 1}$.


-----Input-----

The first line contains three integers $n$, $L$, $S$ ($1 \le n \le 10^5$, $1 \le L \le 10^5$, $1 \le S \le 10^{18}$) — the number of vertices, the maximum number of vertices in one path and the maximum sum in one path.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^9$) — the numbers in the vertices of the tree.

The third line contains $n - 1$ integers $p_2, \ldots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of the $i$-th vertex in the tree.


-----Output-----

Output one number  — the minimum number of vertical paths. If it is impossible to split the tree, output $-1$.


-----Examples-----
Input
3 1 3
1 2 3
1 1

Output
3
Input
3 3 6
1 2 3
1 1

Output
2
Input
1 1 10000
10001

Output
-1


-----Note-----

In the first sample the tree is split into $\{1\},\ \{2\},\ \{3\}$.

In the second sample the tree is split into $\{1,\ 2\},\ \{3\}$ or $\{1,\ 3\},\ \{2\}$.

In the third sample it is impossible to split the tree.

Source: codeforces | Difficulty: VERY_HARD
Tags: Sorting

Greedy algorithms

Tree algorithms

Dynamic programming

Data structures


Solutions:
from collections import defaultdict

def rec(n, l, s):
	dp = [{} for _ in range(n)]
	ans = 0
	for cur in range(n - 1, -1, -1):
		child_of_cur = children.get(cur, None)
		if not child_of_cur:
			dp[cur][1] = weight[cur]
			continue
		ans += len(child_of_cur) - 1
		cur_weight = weight[cur]
		for ch in child_of_cur:
			for (ln, child_weight) in dp[ch].items():
				if ln == l:
					continue
				agg_weight = cur_weight + child_weight
				if agg_weight > s:
					continue
				if ln + 1 not in dp[cur]:
					dp[cur][ln + 1] = agg_weight
				dp[cur][ln + 1] = min(dp[cur][ln + 1], agg_weight)
		if not dp[cur]:
			ans += 1
			dp[cur][1] = weight[cur]
	return ans + 1
weight = []
children = defaultdict(set)
(n, l, s) = map(int, input().split())
for w in map(int, input().split()):
	if w > s:
		print(-1)
		return
	weight.append(w)
if n == 1:
	print(-1 if weight[0] > s else 1)
	return
for (i, v) in enumerate(map(int, input().split())):
	children[v - 1].add(i + 1)
print(rec(n, l, s))


def solve(n, l, s, www, children):
	ans = 0
	dp = [{} for _ in range(n)]
	for v in range(n - 1, -1, -1):
		cv = children[v]
		if not cv:
			dp[v][1] = www[v]
			continue
		ans += len(cv) - 1
		wv = www[v]
		if wv > s:
			return -1
		dv = dp[v]
		for c in cv:
			for (lc, wc) in dp[c].items():
				if lc == l:
					continue
				wt = wc + wv
				if wt > s:
					continue
				if lc + 1 not in dv:
					dv[lc + 1] = wt
				else:
					dv[lc + 1] = min(dv[lc + 1], wt)
		if not dv:
			ans += 1
			dv[1] = wv
	return ans + 1
(n, l, s) = list(map(int, input().split()))
www = list(map(int, input().split()))
if n == 1:
	print(-1 if www[0] > s else 1)
	return
children = [set() for _ in range(n)]
for (i, p) in enumerate(map(int, input().split())):
	children[p - 1].add(i + 1)
print(solve(n, l, s, www, children))


(n, l, s) = map(int, input().split())
(i, ans) = (n, 0)
(w, par, vis) = ([0], [0, 0], [0] * (n + 10))
for u in map(int, input().split()):
	if u > s:
		(print(-1), exit(0))
	w.append(u)
if n > 1:
	for u in map(int, input().split()):
		par.append(u)
while i > 0:
	if vis[i] == 0:
		(c, p, x) = (i, l, s)
		ans = ans + 1
		while x >= w[c] and p * c > 0:
			vis[c] = 1
			p = p - 1
			x = x - w[c]
			c = par[c]
	i = i - 1
print(ans)