#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Project{
ll t,l,r,c;
};
vector<pair<ll,ll>> mergeSeg(vector<pair<ll,ll>> v){
if(v.empty()) return v;
sort(v.begin(),v.end());
vector<pair<ll,ll>> res;
res.push_back(v[0]);
for(int i=1;i<v.size();i++){
if(v[i].first<=res.back().second+1)
res.back().second=max(res.back().second,v[i].second);
else
res.push_back(v[i]);
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
int M;
cin>>N>>M;
vector<Project> p(M);
for(int i=0;i<M;i++)
cin>>p[i].t>>p[i].l>>p[i].r>>p[i].c;
ll ans=LLONG_MAX;
for(ll mask=0; mask<(1LL<<M); mask++){
vector<Project> use;
ll cost=0;
ll maxT=0;
for(int i=0;i<M;i++){
if(mask&(1LL<<i)){
use.push_back(p[i]);
cost+=p[i].c;
maxT=max(maxT,p[i].t);
}
}
if(cost>=ans) continue;
sort(use.begin(),use.end(),[](auto &a,auto &b){
return a.t<b.t;
});
vector<pair<ll,ll>> inf={{1,N}};
int ptr=0;
for(ll day=1; day<=maxT && !inf.empty(); day++){
// noon spread
for(auto &s:inf){
s.first=max(1LL,s.first-1);
s.second=min(N,s.second+1);
}
inf=mergeSeg(inf);
// evening treatments
while(ptr<use.size() && use[ptr].t==day){
ll L=use[ptr].l;
ll R=use[ptr].r;
vector<pair<ll,ll>> nxt;
for(auto [l,r]:inf){
if(r<L || l>R){
nxt.push_back({l,r});
}else{
if(l<L) nxt.push_back({l,L-1});
if(r>R) nxt.push_back({R+1,r});
}
}
inf=mergeSeg(nxt);
ptr++;
}
}
if(inf.empty())
ans=min(ans,cost);
}
if(ans==LLONG_MAX) cout<<-1<<"\n";
else cout<<ans<<"\n";
}
