CF1059E 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, \ldots, v_k $ where $ v_i $ ( $ i \ge 2 $ ) is the parent of $ v_{i - 1} $ .

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 one number — the minimum number of vertical paths. If it is impossible to split the tree, output $ -1 $ .

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.