#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = 2e5 + 12, MOD = (int)1e9 + 7;

const ll inf = 1e18;
ll res = inf;
int n, m;
bool ok(vector<array<int, 4>> &x) {
    if(x.empty()) return false;
    int s = (int)x.size(), f = x.back()[0];
    vector<array<int, 3>> otr;
    vector<pair<int, int>> in;
    for(int i = 0; i < s;) {
        int j = i + 1;
        while(j < s && x[j][0] == x[i][0]) {
            j++;
        }
        vector<pair<int, int>> ff;
        int mx = -2;
        for(int k = i; k < j; ) {
            int nx = k + 1;
            int mx = x[k][2];
            while(nx < j && mx >= x[nx][1] - 1) {
                mx = max(mx, x[nx][2]);
                nx++;
            }
            ff.push_back({x[k][1], mx});
            k = nx;
        }
        for(auto [l, r]:ff) {
            int del = (f - x[i][0]);
            if(l > 1) {
                l += del;
            }
            if(r < n) {
                r -= del;
            }
            if(l <= r) {
                in.push_back({l, r});
            }
        }
        i = j;
    }
    sort(in.begin(), in.end());
    int mx = 0;
    for(auto [l, r]:in) {
        if(l > mx + 1) {
            return false;
        }
        mx = max(mx, r);
    }
    if(mx < n) return false;
    return true;
}
vector<array<int, 4>> a;
void test() {
    cin >> n >> m;
    a.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    }
    sort(a.begin(), a.end());
    for(int i = 0; i < (1 << m); i++) {
        ll c = 0;
        vector<array<int, 4>> x;
        for(int j = 0; j < m; j++) {
            if((i >> j) & 1) {
                c += a[j][3];
                x.push_back(a[j]);
            }
        }
        if(ok(x)) {
            res = min(res, c);
        }
    }

    if(res == inf) {
        res = -1;
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}