阿廖娜决定节食并去森林里拿一些苹果。在那里她意外地发现了一棵神奇的有根树,根在顶点1,每个顶点和每条边上都写着一个数字。
女孩注意到树的一些顶点是悲伤的,所以她决定玩它们。如果顶点 v 的子树中有一个顶点 u 且 dist(v, u) > au,则我们将顶点 v 称为悲伤的,其中 au 是写在顶点 u 上的数字,dist(v, u) 是写在从 v 到 u 的路径上的边上的数字之和。
树的叶子是通过单条边连接到单个顶点的顶点,但树的根当且仅当树由单个顶点(根)组成时才是叶子。
因此,Alyona 决定移除一些树叶,直到树上不再留下任何悲伤的顶点。 Alyona 需要去除的最少叶子数量是多少?
输入
在输入整数 n (1 ≤ n ≤ 105) 的第一行给出 — 树中的顶点数。
第二行给出了 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) 的序列,其中 ai 是写在顶点 i 上的数字。
接下来的 n - 1 行描述了树的边:第 i 行由两个整数 pi 和 ci 组成(1 ≤ pi ≤ n,- 109 ≤ ci ≤ 109),这意味着有一条边连接顶点 i + 1 和 pi,上面写有数字 ci。
输出
打印唯一的整数 - Alyona 需要移除的叶子的最小数量,这样树中就不会有任何悲伤的顶点。
示例
输入 #1
9 88 22 83 14 95 91 98 53 11 3 24 7 -8 1 67 1 64 9 65 5 12 6 -80 3 8
输出 #1
5
注意
下图表示从树上移除叶子的可能过程: