Fancy Antiques

You are throwing a party at your house tomorrow, and you want to decorate the place with antiques.

There are $n$ antiques you want to buy, and the city has $m$ antique shops. The antiques are so rare that exactly one shop in the city sells the original of any given antique. Shops also sell knock-off copies, and for each antique exactly one shop in the city sells the knock-off. The shop that sells the original is not always the shop that sells the knock-off.

Most people cannot tell an original from a knock-off, so either version decorates the house just as well. Each shop sets its own prices, so a knock-off is sometimes more expensive than the original. The party is tomorrow, so you have time to visit at most $k$ shops. For each of the $n$ antiques you must buy exactly one version, original or knock-off, and you can buy it only at a shop you visit.

Consider three shops and three antiques you want to buy.

• Antique 1 sells for 30 at shop 1, and its knock-off sells for 50 at shop 2.
• Antique 2 sells for 70 at shop 2, and its knock-off sells for 10 at shop 3.
• Antique 3 sells for 20 at shop 3, and its knock-off sells for 80 at shop 1.

If you have time for two shops, visit shops 1 and 3. Buy the original of antique 1 for 30 at shop 1, the knock-off of antique 2 for 10 at shop 3, and the original of antique 3 for 20 at shop 3. The total is 60, and no other pair of shops is cheaper. If you have time for one shop, no single shop carries a version of all three antiques, so the trip is impossible.

Find the minimum total cost of buying one version of every antique while visiting at most $k$ shops.

The first line has three space separated integers $n$, $m$, and $k$ ($1 \le n \le 100$, $1 \le k \le m \le 40$): the number of antiques you want, the number of shops in the city, and the number of shops you have time to visit.

Each of the next $n$ lines has four space separated integers $a$, $p$, $b$, and $q$ describing one antique.

• $a$ is the index of the shop that sells the original ($1 \le a \le m$).
• $p$ is the price of the original at shop $a$ ($1 \le p \le 10^7$).
• $b$ is the index of the shop that sells the knock-off ($1 \le b \le m$).
• $q$ is the price of the knock-off at shop $b$ ($1 \le q \le 10^7$).

$a$ and $b$ can be the same shop.

Print the minimum total cost of buying one version of every antique while visiting at most $k$ shops. If no set of at most $k$ shops carries a version of every antique, print -1.