Fancy Antiques

Time limit10sMemory limit512 MB

Summary

Pick at most k shops so that every item can be bought (original or knock-off) at a visited shop, minimizing total price.

Level: Medium7 of 10
Topics: Brute force, Bit manipulation, Greedy, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

Example 1
Input
```
3 3 2
1 30 2 50
2 70 3 10
3 20 1 80
```
Expected output
```
60
```
Example 2
Input
```
3 3 1
1 30 2 50
2 70 3 10
3 20 1 80
```
Expected output
```
-1
```