BajtoCorp 公司刚刚搬进了一栋新建的办公楼。该建筑包含 $n$ 个房间和 $n-1$ 条连接它们的走廊。房间编号为 $1$ 到 $n$，走廊编号为 $1$ 到 $n-1$。任意两个房间之间都有且仅有一条路径（无环）。房间 $i$ 最初有 $a_i$ 个人。走廊 $j$ 的最大通行能力为 $b_j$。

在某些房间必须建造紧急出口，而在其余每个房间中，必须放置一个指向相邻房间的绿色箭头，指示疏散路径。当然，箭头的放置方式应确保沿着箭头的指向，最终能够到达某个紧急出口。在疏散过程中，所有最初位于带有箭头的房间内或进入该房间的人，都会沿着箭头指示的方向移动。疏散路径的规划必须满足：在整个疏散过程中，通过第 $j$ 条走廊的总人数不超过 $b_j$。（我们不知道不同的人通过给定走廊的顺序，因此我们需要为最坏情况做好准备。）我们对通过房间的人数没有限制。

你的任务是确定需要建造的紧急出口的最小数量。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示房间数量。 第二行包含 $n$ 个整数，其中第 $i$ 个数表示 $a_i$ ($1 \le a_i \le 10^{12}$)，即最初位于第 $i$ 个房间的人数。 接下来的 $n-1$ 行描述走廊。第 $j$ 行包含三个整数 $x_j, y_j, b_j$ ($1 \le x_j < y_j \le n, 1 \le b_j \le 10^{18}$)，表示第 $j$ 条走廊连接房间 $x_j$ 和 $y_j$，且在整个疏散过程中通过该走廊的总人数最多为 $b_j$。

输出格式

输出一个整数，表示需要在建筑物中规划的紧急出口的最小数量。

样例

样例输入 1

10
20 30 64 10 4 80 20 5 10 4
1 2 80
2 3 90
3 4 60
4 5 4
5 6 4
2 7 80
3 8 10
4 9 20
5 10 4

样例输出 1

3

说明 1

样例解释：必须在 6 号房间设置一个紧急出口，因为那里有 80 个人，而通往该房间的走廊只能容纳 4 个人。下一个出口可以设置在 2 号或 3 号房间；它将服务于 1, 2, 3, 4, 7, 8, 9 号房间。请注意，10 号房间的 4 个人不能被引导到与 5 号房间的 4 个人不同的方向，而这 8 个人加在一起既不能通过通往 4 号房间的走廊，也不能通过通往 6 号房间的走廊；因此，我们必须在 5 号或 10 号房间设置另一个紧急出口。

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试数据组成。