#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll N, M, sz;
pair<ll, pair<pii, ll>> arr[100005];
ll seg[200505 * 2];
void update(int pos, ll v) {
pos += sz;
seg[pos] = min(seg[pos], v);
for (; pos > 0; pos >>= 1) seg[pos >> 1] = min(seg[pos], seg[pos ^ 1]);
return;
}
ll query(int l, int r) {
r++;
ll ret = inf;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret = min(ret, seg[l++]);
if (r & 1) ret = min(ret, seg[--r]);
}
return ret;
}
void subtask_1() {
vector<ll> v;
v.push_back(0);
v.push_back(1), v.push_back(N);
for (int i = 0; i < M; i++) {
v.push_back(arr[i].second.first.first);
v.push_back(arr[i].second.first.second);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
sz = v.size();
sort(arr, arr + M, [&](pair<ll, pair<pii, ll>> a, pair<ll, pair<pii, ll>> b) {
return a.second.first.second < b.second.first.second;
});
for (int i = 0; i < M; i++) {
ll L = arr[i].second.first.first, R = arr[i].second.first.second;
L = lower_bound(v.begin(), v.end(), L) - v.begin();
R = lower_bound(v.begin(), v.end(), R) - v.begin();
arr[i].second.first = {L, R};
}
vector<ll> dp(sz + 5, inf);
memset(seg, 0x3f, sizeof(seg));
dp[0] = 0;
update(0, dp[0]);
for (int i = 0; i < M; i++) {
ll l = arr[i].second.first.first, r = arr[i].second.first.second, c = arr[i].second.second;
ll idx = lower_bound(v.begin(), v.end(), v[l] - 1) - v.begin();
dp[r] = min(dp[r], query(idx, r) + c);
update(r, dp[r]);
}
int idx = lower_bound(v.begin(), v.end(), N) - v.begin();
if (dp[idx] == inf) cout << -1;
else cout << dp[idx];
return;
}
void subtask_2() {
ll ans = inf;
sort(arr, arr + M);
for (int i = 0; i < (1 << M); i++) {
vector<int> v;
ll cost = 0;
for (int j = 0; j < M; j++) {
if (i & (1 << j)) v.push_back(j), cost += arr[j].second.second;
}
vector<pair<pii, ll>> now;
now.push_back({{1, N}, 0});
for (int j: v) {
vector<pair<pii, ll>> nxt;
ll T = arr[j].first, L = arr[j].second.first.first, R = arr[j].second.first.second;
for (auto &[range, t]: now) {
ll l = range.first, r = range.second;
l -= T - t, l = max(l, 1LL);
r += T - t, r = min(r, N);
if (l < L) nxt.push_back({{l, min(r, L - 1)}, T});
if (r > R) nxt.push_back({{max(l, R + 1), r}, T});
}
swap(nxt, now);
}
if (now.empty()) ans = min(ans, cost);
}
if (ans == inf) cout << -1;
else cout << ans;
return;
}
void solve() {
cin >> N >> M;
int sub_task1 = 1, sub_task2 = (M <= 16);
for (int i = 0; i < M; i++) {
ll T, L, R, C;
cin >> T >> L >> R >> C;
if (T != 1) sub_task1 = 0;
arr[i] = {T, {{L, R}, C}};
}
if (sub_task1) {
subtask_1();
return;
}
if (sub_task2) {
subtask_2();
return;
}
return;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
