有一个国家有 $N$ 个城市。所有这些城市通过带权道路连接，使得任意两个城市之间都存在唯一的一条简单路径。

考虑所有包含 $L$ 到 $R$ 条道路（包含 $L$ 和 $R$）的简单路径。你的任务是找到其中 $k$-value 最小的路径。

简单路径的 $k$-value 计算如下：设路径中的道路数量为 $r$。将路径中所有 $r$ 条道路的权重列表按非降序排列。$k$-value 即为该列表中第 $(\lfloor r/k \rfloor + 1)$ 个元素。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)。接下来的 $(N - 1)$ 行，每行包含三个整数 $a, b$ 和 $w$，表示连接两个城市的一条道路及其权重 ($1 \le a, b \le N, a \neq b, 1 \le w \le 10^9$)。

最后一行包含三个整数 $k, L$ 和 $R$ ($1 < k < 50, 1 \le L \le R \le 50$)。

输出格式

输出包含 $L$ 到 $R$ 条道路（包含 $L$ 和 $R$）的路径中，最小的 $k$-value。如果不存在这样的路径，输出 $-1$。

样例

输入格式 1

5
1 2 1
2 3 2
3 4 3
4 5 4
2 3 4

输出格式 1

2