Fancy Antiques

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k, e = 0;
    cin >> n >> m >> k;

    vector<int> save(m);
    vector<bool> mark(m);
    vector<vector<int>> adj(m);

    for (int i = 0; i < n; i++) {
        int a, p, b, q;
        cin >> a >> p >> b >> q;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        e += max(p, q);
        if (p < q)
            save[a] += q - p;
        else
            save[b] += p - q;
    }

    // helper function
    function<int(int, int, int)> state = [&](int i, int cnt, int savings) -> int {
        // base cases
        if (cnt > k)
            return -1;
        else if (i == m) {
            if (cnt == k)
                return savings;
            else
                return -1;
        }
        else if (mark[i])
            return state(i + 1, cnt, savings);

        int max_s = -1;

        // pick it
        mark[i] = true;
        max_s = state(i + 1, cnt + 1, savings + save[i]);

        // don't pick it
        mark[i] = false;
        vector<int> done;
        for (int& u: adj[i])
            if (!mark[u]) {
                cnt++;
                mark[u] = true;
                savings += save[u];
                done.push_back(u);
            }

        max_s = max(state(i + 1, cnt, savings), max_s);
        for (int& u: done)
            mark[u] = false;

        return max_s;
    };

    int res = state(0, 0, 0);
    if (res == -1)
        cout << -1;
    else
        cout << e - res;

    return 0;
}