/*
 * 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;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:16:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~