Description

On a certain day, Kiana met a boy who dominates the Explosive Mayhem Arena.

Because Kiana has studied OI for a few more years, she can barely explain to this boy some problems she is good at. Specifically, Kiana first poured $n$ unrelated knowledge points into him, and then used her [Data Deletion] technique to forcibly connect these knowledge points.

Since the boy is very strong, for each link Kiana plans to construct, he can figure it out by himself, but it will take more time. Specifically, Kiana has $m$ links. Each link can connect two unrelated knowledge points. If Kiana directly explains the $i$-th link, it takes $t_i$ time; if the boy figures it out himself, it takes $T_i$ time.

To be lazy, Kiana only needs the links she explains or the boy figures out to make all knowledge points directly or indirectly connected. But to ensure teaching quality, Kiana thinks at least $k$ links should be figured out by the boy himself. Since Kiana’s patience is limited, she wants the longest time among all constructed links, regardless of who does them, to be as small as possible.

Now Kiana wants to know, under these conditions, what is the minimal possible value of the maximum time among the constructed links. Since she cannot compute it, she asks you to tell her.

Input Format

The input contains $m+1$ lines.

The first line contains three positive integers $n$, $k$, and $m$, representing the number of knowledge points, the number of links Kiana wants the boy to figure out himself, and the total number of links, respectively.

Then $m$ lines follow. Each line contains four positive integers $a$, $b$, $T_i$, and $t_i$, meaning a link can be constructed between knowledge points $a$ and $b$. If the boy figures out this link himself, it takes $T_i$ time; if Kiana explains it directly, it takes $t_i$ time.

Output Format

The output contains one line.

Print a single positive integer, the minimal possible value of the maximum time among all constructed links.

4 2 5 
1 2 6 5 
1 3 3 1 
2 3 9 4 
2 4 6 1 
3 4 4 2 

4

Hint

For $30\%$ of the testdata, $1 \le n \le 10$, $n-1 \le m \le 15$.

For $60\%$ of the testdata, $1 \le n \le 500$, $n-1 \le m \le 1000$.

For $100\%$ of the testdata, $1 \le k < n \le 10000$, $n-1 \le m \le 20000$.

$1 \le t_i < T_i \le 10^6$.

The testdata guarantees that a feasible solution exists.

Translated by ChatGPT 5