在 IOI 期间，芭堤雅市将举办一场竞赛：2011 年国际赛车奥林匹克竞赛 (IOR)。作为东道主，我们需要为比赛找到最佳路线。

在芭堤雅-春武里大都会区，有 $N$ 个城市，它们由 $N-1$ 条公路组成的网络连接。每条公路都是双向的，连接两个不同的城市，并且具有以公里为单位的整数长度。此外，任意两个城市之间都存在且仅存在一条路径。也就是说，从一个城市到另一个城市，在不重复经过任何城市的情况下，只有一种方式可以通过一系列公路到达。

IOR 有明确的规定，要求比赛路线必须是一条总长度恰好为 $K$ 公里的路径，且起点和终点必须是不同的城市。显然，为了防止碰撞，比赛路线中不得重复使用任何公路（因此也不得重复经过任何城市）。为了最大限度地减少对交通的干扰，路线必须包含尽可能少的公路。

任务

编写一个过程 best_path(N, K, H, L)，它接受以下参数：

• $N$ —— 城市数量。城市编号为 $0$ 到 $N-1$。
• $K$ —— 比赛路线所需的距离。
• $H$ —— 表示公路的二维数组。对于 $0 \le i < N-1$，公路 $i$ 连接城市 $H[i][0]$ 和 $H[i][1]$。
• $L$ —— 表示公路长度的一维数组。对于 $0 \le i < N-1$，公路 $i$ 的长度为 $L[i]$。

你可以假设数组 $H$ 中的所有值都在 $0$ 到 $N-1$ 之间（包含边界），并且该数组描述的公路连接了上述所有城市。你还可以假设数组 $L$ 中的所有值都是 $0$ 到 $1\,000\,000$ 之间的整数（包含边界）。

你的过程必须返回长度恰好为 $K$ 的有效比赛路线中最少的公路数量。如果不存在这样的路线，你的过程必须返回 -1。

样例

样例 1

考虑图 1 所示的情况，其中 $N=4, K=3$， $H=$ 0 1 1 2 1 3 $L=$ 1 2 4

路线可以从城市 0 开始，前往城市 1，并终止于城市 2。其长度将恰好为 $1\text{ km} + 2\text{ km} = 3\text{ km}$，并且由两条公路组成。这是最佳路线；因此 best_path(N, K, H, L) 必须返回 2。

图 1。

样例 2

考虑图 2 所示的情况，其中 $N=3, K=3$， $H=$ 0 1 1 2 $L=$ 1 1

不存在有效的路线。在这种情况下，best_path(N, K, H, L) 必须返回 -1。

图 2。

样例 3

考虑图 3 所示的情况，其中 $N=11, K=12$， $H=$ 0 1 0 2 2 3 3 4 4 5 0 6 6 7 6 8 8 9 8 10 $L=$ 3 4 5 4 6 3 2 5 6 7

一种可能的路线包含 3 条公路：从城市 6 经由城市 0 和城市 2 到达城市 3。另一条路线从城市 10 开始，经由城市 8 到达城市 6。这两条路线的长度都恰好为 12 公里，符合要求。第二条路线是最优的，因为不存在仅包含一条公路的有效路线。因此，best_path(N, K, H, L) 必须返回 2。

图 3。

子任务

子任务 1 (9 分)

• $1 \le N \le 100$
• $1 \le K \le 100$
• 公路网络形成最简单的直线：对于 $0 \le i < N-1$，公路 $i$ 连接城市 $i$ 和 $i+1$。

子任务 2 (12 分)

• $1 \le N \le 1\,000$
• $1 \le K \le 1\,000\,000$

子任务 3 (22 分)

• $1 \le N \le 200\,000$
• $1 \le K \le 100$

子任务 4 (57 分)

• $1 \le N \le 200\,000$
• $1 \le K \le 1\,000\,000$

实现细节

限制

• CPU 时间限制：3 秒
• 内存限制：256 MB 注意：没有明确的栈内存大小限制。栈内存计入总内存使用量。

接口 (API)

• 实现文件夹：race/
• 参赛者需实现：race.c 或 race.cpp 或 race.pas
• 参赛者接口：race.h 或 race.pas
• 评测接口：race.h 或 racelib.pas
• 样例评测程序：grader.c 或 grader.cpp 或 grader.pas
• 样例评测输入：grader.in.1, grader.in.2, ...

注意：样例评测程序按以下格式读取输入： 第 1 行：$N$ 和 $K$。 第 2 行至第 $N$ 行：公路信息；即第 $i+2$ 行包含 $H[i][0], H[i][1]$ 和 $L[i]$，以空格分隔，对于 $0 \le i < N-1$。 第 $N+1$ 行：期望的解。 样例评测输入的期望输出：grader.expect.1, grader.expect.2, … 对于此任务，这些文件中的每一个都应精确包含文本 “Correct.”。