1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int, int> ii;
constexpr int INF = 1e9;

struct node {
	int val; node* c[2];
	node() { val = -INF; c[0] = c[1] = 0; }
	node* get_c(int i) { return (!c[i] ? c[i] = new node : c[i]); }
	void update(int x, int v, int l = 0, int r = INF) {
		if (l == r) val = max(v, val);
		else {
			int m = (l + r) >> 1;
			x <= m ? get_c(0)->update(x, v, l, m) : get_c(1)->update(x, v, m + 1, r);
			val = max(c[0] ? c[0]->val : -INF, c[1] ? c[1]->val : -INF);
		}
	}
	int query(int a, int b, int l = 0, int r = INF) {
		if (a > r || b < l) return -INF;
		if (a <= l && b >= r) return val;
		int m = (l + r) >> 1;
		return max(c[0] ? c[0]->query(a, b, l, m) : -INF, c[1] ? c[1]->query(a, b, m + 1, r) : -INF);
	}
} seg;

pair<ii, ii> A[100001];

int main() {
	ifstream cin("boards.in");
	ofstream cout("boards.out");

	int N, P;
	cin >> N >> P;
	for (int i = 0; i < P; ++i) cin >> A[i].f.f >> A[i].f.s >> A[i].s.f >> A[i].s.s;
	sort(A, A + P);
	
	seg.update(0, 0);
	set<pair<ii, int>> S;
	for (int i = 0; i < P; ++i) {
		S.emplace(A[i].s, A[i].f.f + A[i].f.s - seg.query(0, A[i].f.s));
		auto it = S.begin();
		while (it != S.end() && it->f.f <= (i < P - 1 ? A[i + 1].f.f : INF)) {
			seg.update(it->f.s, it->f.f + it->f.s - it->s);
			it = S.erase(it);
		}		
	}
	cout << 2 * N - seg.query(0, N);
}