Save the Universe

宇宙之间形成一棵以节点 1 为根的树(节点 2..n 的父亲由 p 给出)。第 i 个宇宙有 evilness e[i]。Hero 有一把能量为 m 的枪。每次"开枪"会摧毁一个子树并消除其总 evilness。一个子树被允许保留的条件是其总 evilness < k。求最少开枪次数让全树合法(或将所有节点摧毁)。

Constraints

• Number of universes, n ≤ 10⁵
• The power of the gun, m ≤ 10⁵
• The evilness of each universe and total evilness, K ≤ 10¹⁸

Example 1

Input:

n = 6
m = 3
k = 100
e = [1, 100, 1, 1, 1, 1]
p = [1, 1, 2, 3, 3]

Output:

4

Explanation: