E. DZY любит садоводство
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

DZY любит садоводство, поэтому он обожает решать задачи про деревья.

У DZY есть взвешенное дерево (связный неориентированный граф без циклов), состоящее из n вершин (пронумерованных от 1 до n). Определим функцию g(x, y) (1 ≤ x, y ≤ n) как длину самого длинного ребра в кратчайшем пути между вершинами x и y. В частности, g(z, z) = 0 для любого z.

Для каждой целочисленной последовательности p1, p2, ..., pn (1 ≤ pi ≤ n), определим f(p) как .

DZY хочет найти такую последовательность p, что f(p) принимает максимальное возможное значение. Есть еще одно ограничение: элемент j может встречаться в p не более xj раз.

Пожалуйста, помогите DZY, найдите максимальное возможное f(p) при описанных ограничениях.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 3000).

В каждой из следующих n - 1 строк записано по три целых числа ai, bi, ci (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ 10000), обозначающих ребро между вершинами ai и bi длины ci. Гарантируется, что эти ребра образуют дерево.

Каждая из следующих n строк описывает элемент последовательности x. В j-й строке записано целое число xj (1 ≤ xj ≤ n).

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
4
1 2 1
2 3 2
3 4 3
1
1
1
1
Выходные данные
2
Входные данные
4
1 2 1
2 3 2
3 4 3
4
4
4
4
Выходные данные
3
Примечание

В первом примере одна из оптимальных последовательностей p равна [4, 3, 2, 1].