BajtoCorp is moving into a newly constructed building. The building consists of $n$ rooms and $n-1$ corridors connecting them. The rooms are numbered from $1$ to $n$, and the corridors from $1$ to $n-1$. There is exactly one path between any pair of rooms (without backtracking). Initially, there are $a_i$ people in room $i$. Corridor $j$ has a maximum capacity of $b_j$.

In some rooms, emergency exits must be built, while in each of the remaining rooms, exactly one green arrow must be placed, pointing the way to an evacuation route to one of the adjacent rooms. Naturally, the arrows should be placed such that following them leads to an emergency exit. In the event of an evacuation, all people initially located in a room with an arrow or entering it will move in the direction indicated by the arrow. The evacuation routes must be planned in such a way that the total number of people passing through the $j$-th corridor during the entire evacuation does not exceed $b_j$. (We do not know the order in which different people will pass through a given corridor, so we want to prepare for the worst-case scenario.) We do not impose any restrictions on the number of people that can pass through the rooms.

Your task is to determine the minimum number of emergency exits that must be built.

Input

The first line of the input contains a single integer $n$ ($2 \le n \le 1\,000\,000$), representing the number of rooms. The second line contains $n$ integers; the $i$-th of them is $a_i$ ($1 \le a_i \le 10^{12}$), the number of people initially in the $i$-th room. The next $n-1$ lines contain the description of the corridors. The $j$-th of these lines contains three integers $x_j, y_j, b_j$ ($1 \le x_j < y_j \le n$, $1 \le b_j \le 10^{18}$), meaning that the $j$-th corridor connects rooms $x_j$ and $y_j$, and a total of at most $b_j$ people can pass through it during the entire evacuation.

Output

Output a single integer – the minimum number of emergency exits that must be planned in the building.

Examples

Input 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

Output 1

3

Note

One emergency exit must be located in room number 6, because the 80 people there cannot pass through a corridor that only holds 4 people. Another exit can be placed in room number 2 or 3; it will serve rooms 1, 2, 3, 4, 7, 8, and 9. Note that the 4 people from room number 10 cannot be directed in a different direction than the 4 people from room number 5, and these 8 people together cannot pass to either room number 4 or room number 6; therefore, another emergency exit must be placed in room number 5 or 10.

Subtasks