고급 골동품

내일 집에서 파티를 연다. 파티 장소인 집을 꾸미려고 골동품을 사기로 했다.

사려는 골동품은 $n$개이고, 도시에는 골동품 가게가 $m$개 있다. 골동품은 아주 희귀해서 각 골동품의 진품을 파는 가게는 도시에 하나뿐이다. 가게는 모조품도 파는데, 각 골동품의 모조품을 파는 가게 역시 도시에 하나뿐이다. 진품을 파는 가게와 모조품을 파는 가게가 늘 다른 것은 아니다.

대부분의 사람은 진품과 모조품을 구별하지 못하므로 어느 쪽을 사도 장식 효과는 똑같다. 값은 가게가 정하기 때문에 모조품이 진품보다 비싼 경우도 있다. 파티가 내일이라 가게는 최대 $k$곳까지만 들를 수 있다. 골동품 $n$개마다 진품이나 모조품 중 한 가지를 사야 하고, 물건은 직접 들른 가게에서만 살 수 있다.

가게가 3개, 사려는 골동품이 3개인 경우를 보자.

• 골동품 1의 진품은 가게 1에서 30, 모조품은 가게 2에서 50이다.
• 골동품 2의 진품은 가게 2에서 70, 모조품은 가게 3에서 10이다.
• 골동품 3의 진품은 가게 3에서 20, 모조품은 가게 1에서 80이다.

들를 수 있는 가게가 2곳이면 가게 1과 가게 3을 고른다. 가게 1에서 골동품 1의 진품을 30에, 가게 3에서 골동품 2의 모조품을 10에, 가게 3에서 골동품 3의 진품을 20에 산다. 합계는 60이고, 다른 어떤 두 가게를 골라도 이보다 싸지 않다. 들를 수 있는 가게가 1곳이면 세 골동품을 모두 갖춘 가게가 없으므로 불가능하다.

가게를 최대 $k$곳 들러서 골동품마다 한 가지씩 사는 최소 비용을 구하라.

첫째 줄에 정수 $n$, $m$, $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 100$, $1 \le k \le m \le 40$). $n$은 사려는 골동품 개수, $m$은 도시의 가게 개수, $k$는 들를 수 있는 가게 개수다.

다음 $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$).

$a$와 $b$는 같을 수 있다.

가게를 $k$곳 이하로 들러서 골동품마다 한 가지씩 사는 최소 비용을 출력한다. 그렇게 살 수 없으면 -1을 출력한다.