给你一棵在 $$$n$$$ 个顶点上的有根树,它的根是顶点号 $$$1$$$。第 $$$i$$$ 个顶点包含数字 $$$w_i$$$。将其分割为尽可能少的垂直路径,使得每条路径包含不超过 $$$L$$$ 个顶点,并且每条路径上的整数 $$$w_i$$$ 之和不超过 $$$S$$$。每个顶点应该恰好属于一条路径。
垂直路径是一系列顶点 $$$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$$$。
示例
输入 #1
3 1 3 1 2 3 1 1
输出 #1
3
输入 #2
3 3 6 1 2 3 1 1
输出 #2
2
输入 #3
1 1 10000 10001
输出 #3
-1
注意
在第一个示例中,树被分为 $$$\{1\}、\ \{2\}、\ \{3\}$$$。
在第二个示例中,树被拆分为 $$$\{1,\ 2\},\ \{3\}$$$ 或 $$$\{1,\ 3\},\ \{2\}$$$。
在第三个示例中,不可能拆分树。