Description

图论大师 yyjj 有一棵大小为 $n$ 的树，节点由 $1$ 到 $n$ 编号，其中节点 $1$ 为根节点，相连的节点 $u_i$ 和 $v_i$ 的边的边长为 $w_i$，节点 $u_i$ 可以覆盖以 $u_i$ 为根节点的子树中与它距离小于等于 $d_{u_i}$ 的节点（包括自身）。

yyjj 现在想选择一个节点，使得被该节点覆盖的节点数量最多，请你帮助 yyjj 找出能覆盖的最大节点数量。

Format

Input

第一行一个正整数 $n$ $(1 \leq n \leq 2 \times 10^5)$，表示节点数量。

第二行 $n$ 个正整数 $d_1, d_2, \cdots, d_n$ $(1 \leq d_i \leq 10^9)$，$d_i$ 表示节点 $i$ 的覆盖距离。

接下来 $n - 1$ 行，每行三个正整数 $u_i, v_i, w_i$ $(1 \leq u_i, v_i \leq n; 1 \leq w_i \leq 10^9)$，表示 $u_i$ 与 $v_i$ 之间有一条长为 $w_i$ 的边相连。

Output

一行一个正整数，表示只选择一个节点所能覆盖的最大节点数量。

Samples

10
20 13 5 14 4 16 4 5 20 1
1 6 6
1 4 16
1 3 13
4 8 15
5 6 16
4 7 11
6 10 11
1 2 18
6 9 3

7

Note

在第一个样例中，选择 $1$ 号节点能覆盖到 $7$ 个节点：$1,2,3,4,6,9,10$。

Limitation

1s, 1024KiB for each test case.