你要举办一场盛大的派对来招待朋友们。和所有盛大的派对一样，你需要购买一些精美的古董来装饰场地（你的家）。

城里有 $n$ 件你需要购买的精美古董，还有 $m$ 家古董店。由于这些古董极其稀有，每件古董只能在唯一的一家古董店里找到。然而，这些古董店也会出售其中一些古董的“仿制品”（复制品）。当然，对于任何一件古董，城里也只有唯一的一家古董店出售其仿制品（这是为了保持古董的稀有性）。出售原版的商店并不总是与持有仿制品的商店相同。

事实证明，尽管你能分辨出区别，但大多数人无法分辨出任何给定古董的原版和仿制品。而且，由于商店可以从中获利，有时仿制品比原版还要贵！由于派对明天就要举行，你只有时间去逛 $k$ 家商店。你希望购买 $n$ 件古董中的每一件的一个版本（原版或仿制品）。

假设有三家商店，我们想购买三件古董。 古董 #1 在商店 #1 的售价为 30。其仿制品在商店 #2 的售价为 50。 古董 #2 在商店 #2 的售价为 70。其仿制品在商店 #3 的售价为 10。 * 古董 #3 在商店 #3 的售价为 20。其仿制品在商店 #1 的售价为 80。

假设你只有时间去两家商店。你可以去商店 1 和商店 3。你可以在商店 1 以 30 的价格购买古董 1 的原版，在商店 3 以 20 的价格购买古董 3 的原版，并在商店 3 以 10 的价格购买古董 2 的仿制品。购买这些物品的总成本为 60，这是可能的最小值。

如果你只有时间去一家商店，那么这是不可能的。你无法通过只访问一家商店来买齐所有三件物品的版本。

给定各商店中古董/仿制品的成本，购买每件古董的一个版本所需的最低总成本是多少？

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。输入的第一行包含三个用空格分隔的整数：$n$、$m$ 和 $k$ ($1 \le n \le 100, 1 \le k \le m \le 40$)。接下来的 $n$ 行，每行包含四个用空格分隔的整数 $a, p, b, q$，描述一件古董，其中：

• $a$ 是出售该古董原版的商店编号 ($1 \le a \le m$)
• $p$ 是该古董原版在商店 $a$ 的价格 ($1 \le p \le 10^7$)
• $b$ 是出售该古董仿制品的商店编号 ($1 \le b \le m$)
• $q$ 是该古董仿制品在商店 $b$ 的价格 ($1 \le q \le 10^7$)

输出格式

如果可以在访问不超过 $k$ 家商店的情况下收集到所有古董，则输出最低成本。如果不可能，则输出 $-1$。

样例

样例输入 1

3 3 2
1 30 2 50
2 70 3 10
3 20 1 80

样例输出 1

60

样例输入 2

3 3 1
1 30 2 50
2 70 3 10
3 20 1 80

样例输出 2

-1