[HNOI2006]公路修建问题

OI Island 是一座美丽的岛屿，自开发以来吸引了许多游客。然而，由于岛屿开发时间不长，交通状况仍然十分糟糕。为此，OIER Association 成立了，旨在建设 OI Island 的交通系统。

岛上共有 $n$ 个旅游景点，编号为 $1$ 到 $n$。OIER Association 需要修建公路，使这些景点相互连通。每条公路连接两个景点，并且可以修建为一级公路或二级公路。一级公路的行车速度更快，但修建费用也更高。

OIER Association 计划修建 $n-1$ 条公路，使任意两个景点之间都存在一条路径。为了保证公路系统的效率，这 $n-1$ 条公路中至少要有 $k$ 条一级公路，其中 $0\le k\le n-1$。

在满足上述条件的前提下，OIER Association 希望费用最高的一条公路的费用尽可能小。你的任务是在给定的候选公路中选择 $n-1$ 条公路，并决定它们的等级，使其满足要求。

输入格式

第一行包含三个整数 $n$、$k$、$m$。共有 $m-1$ 条候选公路。

接下来 $m-1$ 行，每行包含四个整数 $a$、$b$、$c_1$、$c_2$，表示景点 $a$ 与景点 $b$ 之间有一条候选公路。将其修建为一级公路的费用为 $c_1$，修建为二级公路的费用为 $c_2$。

保证忽略公路等级后，给出的 $m-1$ 条候选公路能够使全部 $n$ 个景点连通，因此满足要求的方案一定存在。

输出格式

输出一个整数，表示所有满足条件的方案中，费用最高的一条公路的最小可能费用。

特别地，当 $n=1$ 时，输出 $0$。

样例输入

10 4 20
3 9 6 3
1 3 4 1
5 3 10 2
8 9 8 7
6 8 8 3
7 1 3 2
4 9 9 5
10 8 9 1
2 6 9 1
6 7 9 8
2 6 2 1
3 8 9 5
3 2 9 6
1 6 10 3
5 6 3 1
2 7 6 1
7 8 6 2
10 9 2 1
7 1 10 2

样例输出

5

数据范围

• $1\le n\le 10^4$；
• $0\le k\le n-1$；
• $n\le m\le 2\times 10^4$；
• $1\le a,b\le n$，且 $a\ne b$；
• $1\le c_2\le c_1\le 3\times 10^4$；
• 忽略公路等级后，所有候选公路能够使 $n$ 个景点连通。

来源与许可

本题为 HNOI 2006 试题「公路修建问题」，题面与测试数据整理自 BZOJ。

样例 1

输入

10 4 20
3 9 6 3
1 3 4 1
5 3 10 2
8 9 8 7
6 8 8 3
7 1 3 2
4 9 9 5
10 8 9 1
2 6 9 1
6 7 9 8
2 6 2 1
3 8 9 5
3 2 9 6
1 6 10 3
5 6 3 1
2 7 6 1
7 8 6 2
10 9 2 1
7 1 10 2

输出

5