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.

Difficulty: interview

Starter code:

Solutions:
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 list(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))


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))

from collections import defaultdict


def rec(n, l, s):
    # dp[i] is a doctionary, where key is the chain length
    # and value is the weight at node i
    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))

from collections import defaultdict
import sys


def rec(n, l, s):
    # dp[i] is a doctionary, where key is the chain length
    # and value is the weight at node i
    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, sys.stdin.readline().split())
for w in map(int, sys.stdin.readline().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, sys.stdin.readline().split())):
    children[v -1].add(i + 1)
print(rec(n,l,s))