You are hosting a fancy party for fancy friends. And, like
any fancy party, you need to buy some fancy antiques to put up
around the venue (your house).
There is a set of $n$
fancy antiques that you need to buy. And there is a set of
$m$ fancy antique shops in
the city. Because these antiques are extremely rare, each fancy
antique can only be found at a single fancy antique shop.
However, the fancy antique shops can also sell “knockoff”
(duplicate) versions of some of the antiques. And of course,
for any fancy antique, there is only a single fancy antique
shop in the city that holds a knockoff version of that antique
(this is to maintain the rareness of the antiques). The shop
that sells the original is not always the same shop that holds
the knockoff.
It turns out that even though you can tell the difference,
most people cannot tell the original version from the knockoff
version of any given antique. And, because the shops can get
away with it, sometimes the knockoff is more expensive than
the original! Since the party is tomorrow, you only have time
to visit $k$ shops. You
would like to buy one version (either the original or the
knockoff) of each of the $n$ antiques.
Suppose that there are three shops, and three antiques we
would like to buy.

Antique $\# 1$
sells for $30$ at shop
$\# 1$. Its knockoff
sells for $50$ at shop
$\# 2$.

Antique $\# 2$
sells for $70$ at shop
$\# 2$. Its knockoff
sells for $10$ at shop
$\# 3$.

Antique $\# 3$
sells for $20$ at shop
$\# 3$. Its knockoff
sells for $80$ at shop
$\# 1$.
Suppose you only have time to go to two shops. You can go to
shops $1$ and $3$. You can buy the original of
antique $1$ with cost
$30$ at shop $1$, the original of antique
$3$ with cost $20$ at shop $3$, and the knockoff of antique
$2$ at shop $3$ with cost $10$. The total cost to buy these
items is $60$, which is
the minimum possible.
If you only have time to visit one shop, then it is
impossible. You cannot buy a version of all three items by
visiting a single shop.
Given the costs of the antiques/knockoffs at the shops,
what is the minimum total cost to buy one version of each
antique?
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs. The
first line of input will consist of three spaceseparated
integers: $n$,
$m$, and $k$ ($1
\le n \le 100$, $1 \le k
\le m \le 40$). The next $n$ lines will each have four space
separated integers, $a$,
$p$, $b$ and $q$, describing an antique, where:

$a$ is the index of
the shop that sells the original version of the antique
($1 \le a \le m$)

$p$ is the price of
the original version of the antique at shop $a$ ($1 \le p \le 10^7$)

$b$ is the index of
the shop that sells the knockoff version of the antique
($1 \le b \le m$)

$q$ is the price of
the knockoff version of the antique at shop $b$ ($1 \le q \le 10^7$)
Output
If it is possible to collect all of the antiques while
visiting no more than $k$
stores, then output the minimum cost. If it is not possible,
output $1$.
Sample Input 1 
Sample Output 1 
3 3 2
1 30 2 50
2 70 3 10
3 20 1 80

60

Sample Input 2 
Sample Output 2 
3 3 1
1 30 2 50
2 70 3 10
3 20 1 80

1
