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

Codeforces Round 514 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

dp

greedy

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Split the Tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/22/2024 14:33:34 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|