DZY 热爱种植,他喜欢解决树木问题。
DZY 有一个包含 n 个节点(编号从 1 到 n)的加权树(无环的连通无向图)。他将函数 g(x, y) (1 ≤ x, y ≤ n) 定义为节点 x 和 y 之间最短路径中的最长边。特别是对于每个 z,g(z, z) = 0。
对于每个整数序列 p1, p2, ..., pn (1 ≤ pi ≤ n),DZY 将 f(p) 定义为 $$\min_{i=1}^{n} g(i,p_i)$$。
DZY 想要找到这样一个序列 p,使得 f(p) 具有最大可能值。但还有一个限制:元素 j 最多只能在 p 中出现 xj 次。
请找出在所描述的限制下可能的最大 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)。
输出
打印代表答案的单个整数。
示例
输入 #1
4 1 2 1 2 3 2 3 4 3 1 1 1 1
输出 #1
2
输入 #2
4 1 2 1 2 3 2 3 4 3 4 4 4 4
输出 #2
3
注意
在第一个样本中,最佳 p 之一是 [4, 3, 2, 1]。