E. Split the Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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}.InputThe 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.OutputOutput one number  — the minimum number of vertical paths. If it is impossible to split the tree, output -1.ExamplesInput3 1 31 2 31 1Output3Input3 3 61 2 31 1Output2Input1 1 1000010001Output-1NoteIn 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.
Input3 1 31 2 31 1
Output3
['binary search', 'data structures', 'dp', 'greedy', 'trees', '*2400']