// Arup Guha
// 4/28/2016
// Solution to 2016 NAIPC Problem A: Fancy Antiques

import java.util.*;

public class a {

	// The largest viable solution is 10^9, exactly.
	final public static int NO_SOL = 1000000001;
	final public static int UNKNOWN = 2;
	final public static int USED = 1;
	final public static int NOTUSED = 0;

	// Main parameters.
	public static int numAntiques;
	public static int numShops;
	public static int maxShops;

	// Stores lists by shop.
	public static ArrayList<Integer>[] antiqueNum;
	public static ArrayList<Integer>[] antiquePrice;

	// Stores info for each antique.
	public static int[][] antiqueStoreList;
	public static int[][] antiquePriceList;

	// This is critical. forcelist[i] stores which shops we MUST go to, if we choose to skip shop i.
	public static ArrayList<Integer>[] forcelist;

	public static void main(String[] args) {

		// Read in basic data.
		Scanner stdin = new Scanner(System.in);
		numAntiques = stdin.nextInt();
		numShops = stdin.nextInt();
		maxShops = stdin.nextInt();

		// Allocate all of our space.
		antiqueStoreList = new int[numAntiques][2];
		antiquePriceList = new int[numAntiques][2];
		forcelist = new ArrayList[numShops];
		antiqueNum = new ArrayList[numShops];
		antiquePrice = new ArrayList[numShops];
		for (int i=0; i<numShops; i++) {
			forcelist[i] = new ArrayList<Integer>();
			antiqueNum[i] = new ArrayList<Integer>();
			antiquePrice[i] = new ArrayList<Integer>();
		}

		// Read in the rest of the antique data.
		for (int i=0; i<numAntiques; i++) {

			// Read by antique, also store by store.
			for (int j=0; j<2; j++) {
				antiqueStoreList[i][j] = stdin.nextInt()-1;
				antiquePriceList[i][j] = stdin.nextInt();
				antiqueNum[antiqueStoreList[i][j]].add(i);
				antiquePrice[antiqueStoreList[i][j]].add(antiquePriceList[i][j]);
			}

			// Since I run my brute force forwards, I only need to store this in one direction.
			int a = antiqueStoreList[i][0];
			int b = antiqueStoreList[i][1];
			forcelist[Math.min(a,b)].add(Math.max(a,b));
		}

		// Set up function, call it.
		int[] curShops = new int[numShops];
		Arrays.fill(curShops, UNKNOWN);
		int[] spent = new int[numAntiques];
		Arrays.fill(spent, NO_SOL);
		boolean[] used = new boolean[numAntiques];
		int res = f(curShops, 0, 0, spent, 0, 0);

		// Output result.
		if (res == NO_SOL)
			System.out.println(-1);
		else
			System.out.println(res);
	}

	public static int f(int[] curShops, int k, int shopCnt, int[] spent, int curCost, int usedCnt) {

		// Base cases.
		if (shopCnt > maxShops) return NO_SOL;
		if (k >= numShops || shopCnt == maxShops) return usedCnt == numAntiques ? curCost : NO_SOL;

		// Last base case - we've already made a decision on this shop.
		if (curShops[k] == USED) return f(curShops, k+1, shopCnt, spent, curCost, usedCnt);

		int res = usedCnt == numAntiques ? curCost : NO_SOL;

		// First let's try NOT going to shop k.
		curShops[k] = NOTUSED;
		int addedAntiques = 0;
		int addedShops = 0;
		int saveCurCost = curCost;
		int[] savespent = Arrays.copyOf(spent, spent.length);
		int[] saveCurShops = Arrays.copyOf(curShops, curShops.length);

		// We only enter this case if we aren't forced into this shop.
		if (!forcelist[k].contains(k) && antiqueNum[k].size() > 0) {

			// Add in each shop (if not already added) to our list that we have to add if we don't take shop k.
			for (int i=0; i<forcelist[k].size(); i++) {

				int next = forcelist[k].get(i);

				// We only add ones that we haven't added before.
				if (curShops[next] == UNKNOWN) {

					curShops[next] = USED;
					addedShops++;

					// Go through each antique in this shop.
					for (int j=0; j<antiqueNum[next].size(); j++) {
						int thisAntique = antiqueNum[next].get(j);

						// We don't have this one, get it!
						if (spent[thisAntique] == NO_SOL) {
							addedAntiques++;
							spent[thisAntique] = antiquePrice[next].get(j);
							curCost += spent[thisAntique];
						}

						// We have it, but we can get a better version, so get it!
						else if (antiquePrice[next].get(j) < spent[thisAntique]) {
							int old = spent[thisAntique];
							spent[thisAntique] = antiquePrice[next].get(j);
							curCost = curCost - old + spent[thisAntique];
						}
					}
				}

				// This is a contradiction.
				else if (curShops[next] == NOTUSED) {
					return NO_SOL;
				}

			} // end i loop

			// Now, we can make our recursive call after adding our forced shops.
			res = Math.min(res, f(curShops, k+1, shopCnt+addedShops, spent, curCost, usedCnt+addedAntiques));
		}

		// Now, we must try going to shop k.
		curShops = Arrays.copyOf(saveCurShops, curShops.length);
		curShops[k] = USED;
		addedAntiques = 0;
		spent = Arrays.copyOf(savespent, spent.length);
		curCost = saveCurCost;

		// Go through each antique in this shop.
		for (int j=0; j<antiqueNum[k].size(); j++) {
			int thisAntique = antiqueNum[k].get(j);

			// We don't have this one, get it!
			if (spent[thisAntique] == NO_SOL) {
				addedAntiques++;
				spent[thisAntique] = antiquePrice[k].get(j);
				curCost += spent[thisAntique];
			}

			// We have it, but we can get a better version, so get it!
			else if (antiquePrice[k].get(j) < spent[thisAntique]) {
				int old = spent[thisAntique];
				spent[thisAntique] = antiquePrice[k].get(j);
				curCost = curCost - old + spent[thisAntique];
			}
		}

		int newShopCnt = antiqueNum[k].size() > 0 ? shopCnt + 1 : shopCnt;

		// Return the better of these two options.
		return Math.min(res, f(curShops, k+1, newShopCnt, spent, curCost, usedCnt+addedAntiques));
	}
}