/*
* author: ADMathNoob
* created: 08/14/24 22:28:48
* problem: https://qoj.ac/problem/6455
*/
/*
Comments about problem:
*/
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif
const int M = 40;
int n, m, k;
vector<int> g[M];
int bonus[M];
bool has_self[M];
int state[M];
vector<int> order;
int Solve(int z, int used, int cur) {
assert(used <= k);
if (z == m) {
return cur;
}
int v = order[z];
if (state[v] != -1) {
if (state[v] == 1) {
cur += bonus[v];
}
return Solve(z + 1, used, cur);
}
int res = -1;
if (!has_self[v]) {
state[v] = 0;
vector<int> changed;
for (int u : g[v]) {
assert(state[u] != 0);
if (state[u] == -1) {
state[u] = 1;
changed.push_back(u);
}
}
int new_used = used + changed.size();
if (new_used <= k) {
res = max(res, Solve(z + 1, new_used, cur));
}
for (int u : changed) {
state[u] = -1;
}
changed.clear();
}
if (used < k) {
state[v] = 1;
res = max(res, Solve(z + 1, used + 1, cur + bonus[v]));
}
state[v] = -1;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
int base = 0;
vector<int> deg(m);
for (int i = 0; i < n; i++) {
int x, px, y, py;
cin >> x >> px >> y >> py;
--x; --y;
if (x == y) {
has_self[x] = true;
} else {
g[x].push_back(y);
g[y].push_back(x);
deg[x] += 1;
deg[y] += 1;
}
base += max(px, py);
if (px < py) {
bonus[x] += py - px;
} else {
bonus[y] += px - py;
}
}
order.resize(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y) {
return deg[x] > deg[y];
});
fill(state, state + m, -1);
int max_save = Solve(0, 0, 0);
if (max_save == -1) {
cout << -1 << '\n';
} else {
int ans = base - max_save;
cout << ans << '\n';
}
return 0;
}