Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

E. Split the Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.