题目描述

你正在为你的时髦朋友们举办一场时髦派对。和任何时髦派对一样，你需要购买一些时髦的古董来摆放在场地（也就是你的房子）周围。

你需要购买 $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 \leq n \leq 100$，$1 \leq k \leq m \leq 40$）。接下来的 $n$ 行，每行包含四个空格分隔的整数 $a$、$p$、$b$ 和 $q$，描述一件古董，其中：

• $a$ 是销售该古董原版的商店编号（$1 \leq a \leq m$）
• $p$ 是该古董在商店 $a$ 的原版价格（$1 \leq p \leq 10^7$）
• $b$ 是销售该古董仿制版的商店编号（$1 \leq b \leq m$）
• $q$ 是该古董在商店 $b$ 的仿制版价格（$1 \leq q \leq 10^7$）

输出格式

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

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

60

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

-1

提示

翻译由 DeepSeek V3.2 完成