题目描述

某年某月某日，Kiana 结识了一名爆弹虐场的少年。

Kiana 仗着自己多学了几年 OI，所以还可以勉勉强强给这位少年讲一些自己擅长的题。具体来说，Kiana 先给这位少年灌输了 $n$ 个毫不相干的知识点，然后再通过自己的[数据删除]技术把这些知识点强行联系在一起。

由于这位少年有着爆弹虐场的实力，所以对于每个 Kiana 准备强行构造的联系，他都能够自己想出来，不过会花费更多的时间。具体来说，Kiana 一共有 $m$ 个联系，每个联系可以把两个不相干的知识点连在一起，如果由 Kiana 直接来讲第 $i$ 个联系，需要花费 $t_i$ 的时间，而如果由少年自己想出来，则需要花费 $T_i$ 的时间。

为了偷懒，Kiana 只需要自己讲的或少年想出来的联系能刚好把知识点全部直接或间接串在一起就可以了。但为了保证教学质量，Kiana 觉得至少有 $k$ 个联系需要少年自己想出来。由于 Kiana 耐心有限，她希望无论是自己讲或是少年自己想，构造的联系中花费时间最长的一个用时最短。

现在 Kiana 想知道，满足这些条件的情况下，构造的联系中耗时最长的一个的最短用时是多少。由于她不会算，所以希望由你告诉她。

输入格式

输入文件包括 $m+1$ 行。

第一行包含三个正整数 $n$，$k$ 和 $m$，分别表示知识点的数量，Kiana 希望少年自己想出来的联系的数量和联系的总数量。

接下来 $m$ 行，每行包含四个正整数 $a$，$b$，$T_i$ 和 $t_i$，表示在知识点 $a$ 和 $b$ 之间可以构造出一个联系，这个联系由少年自己想出来需要花费 $T_i$ 的时间，而 Kiana 直接讲出来需要花费 $t_i$ 的时间。

输出格式

输出文件包括一行。

第一行包含一个正整数，表示构造的联系中耗时最长的一个的最短用时。

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

4

提示

对于 $30\%$ 的数据，$1\le n\le 10,n-1\le m\le 15$，

对于 $60\%$ 的数据，$1\le n\le 500,n-1\le m\le 1000$，

对于 $100\%$ 的数据，$1\le k<n\le10000,n-1\le m\le20000$，

$1\le t_i<T_i\le10^6$。

数据保证一定存在可行解。