E. Разбейте дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево на $$$n$$$ вершинах, его корень имеет номер $$$1$$$. В $$$i$$$-й вершине записано число $$$w_i$$$. Разбейте его на минимальное число таких вертикальных путей, что сумма чисел $$$w_i$$$ в вершинах пути не превосходит $$$S$$$, а количество вершин в пути не превосходит $$$L$$$. Каждая вершина должна принадлежать ровно одному пути.

Вертикальным путём называется последовательность вершин $$$v_1, v_2, \ldots, v_k$$$, где $$$v_i$$$ ($$$i \ge 2$$$) — непосредственный предок $$$v_{i - 1}$$$ в дереве.

Входные данные

В первой строке даны целые числа $$$n$$$, $$$L$$$, $$$S$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le L \le 10^5$$$, $$$1 \le S \le 10^{18}$$$) — число вершин в дереве, максимальная длина пути, максимальная сумма на пути.

Во второй строке содержатся $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$) — числа, записанные в вершинах.

Третья строка содержит $$$n - 1$$$ целое число $$$p_2, \ldots, p_n$$$ ($$$1 \le p_i < i$$$), где $$$p_i$$$ обозначает непосредственного предка $$$i$$$-й вершины.

Выходные данные

Выведите одно целое число — минимальное число вертикальных путей. Если разбить дерево невозможно, выведите $$$-1$$$.

Примеры
Входные данные
3 1 3
1 2 3
1 1
Выходные данные
3
Входные данные
3 3 6
1 2 3
1 1
Выходные данные
2
Входные данные
1 1 10000
10001
Выходные данные
-1
Примечание

В первом примере дерево разбивается на пути $$$\{1\},\ \{2\},\ \{3\}$$$.

Во втором примере дерево разбивается на пути $$$\{1,\ 2\},\ \{3\}$$$ или $$$\{1,\ 3\},\ \{2\}$$$.

В третьем примере разбить дерево невозможно.