1059_E. Split the Tree
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, …, v_k where v_i (i ≥ 2) is the parent of v_{i - 1}.

Input

The first line contains three integers n, L, S (1 ≤ n ≤ 10^5, 1 ≤ L ≤ 10^5, 1 ≤ S ≤ 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, …, w_n (1 ≤ w_i ≤ 10^9) — the numbers in the vertices of the tree.

The third line contains n - 1 integers p_2, …, p_n (1 ≤ 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.
```python
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)
        exit()
    weight.append(w)
if n == 1:
    print(-1 if weight[0] > s else 1)
    exit()
for i, v in enumerate(map(int, sys.stdin.readline().split())):
    children[v -1].add(i + 1)
print(rec(n,l,s))
```