Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. DZY Loves Planting

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDZY loves planting, and he enjoys solving tree problems.

DZY has a weighted tree (connected undirected graph without cycles) containing *n* nodes (they are numbered from 1 to *n*). He defines the function *g*(*x*, *y*) (1 ≤ *x*, *y* ≤ *n*) as the longest edge in the shortest path between nodes *x* and *y*. Specially *g*(*z*, *z*) = 0 for every *z*.

For every integer sequence *p*_{1}, *p*_{2}, ..., *p*_{n} (1 ≤ *p*_{i} ≤ *n*), DZY defines *f*(*p*) as .

DZY wants to find such a sequence *p* that *f*(*p*) has maximum possible value. But there is one more restriction: the element *j* can appear in *p* at most *x*_{j} times.

Please, find the maximum possible *f*(*p*) under the described restrictions.

Input

The first line contains an integer *n* (1 ≤ *n* ≤ 3000).

Each of the next *n* - 1 lines contains three integers *a*_{i}, *b*_{i}, *c*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*; 1 ≤ *c*_{i} ≤ 10000), denoting an edge between *a*_{i} and *b*_{i} with length *c*_{i}. It is guaranteed that these edges form a tree.

Each of the next *n* lines describes an element of sequence *x*. The *j*-th line contains an integer *x*_{j} (1 ≤ *x*_{j} ≤ *n*).

Output

Print a single integer representing the answer.

Examples

Input

4

1 2 1

2 3 2

3 4 3

1

1

1

1

Output

2

Input

4

1 2 1

2 3 2

3 4 3

4

4

4

4

Output

3

Note

In the first sample, one of the optimal *p* is [4, 3, 2, 1].

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2021 02:22:02 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|