#include <bits/stdc++.h> #define ll long long using namespace std; const int NMAX = 1e5; const int INF = 2e9; int k, n, cnt_left, cnt_right, ind; ll answer_c, answer, sum_inside, sum_left, sum_right; pair<int, int> v[NMAX + 1]; struct Event { int x, type, pos; }events[2 * NMAX + 1]; bool cmp(const Event& a, const Event& b) { return a.x < b.x; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> n; for(int i = 1; i <= n; i++) { char p, q; int a, b; cin >> p >> a >> q >> b; if(a > b) { swap(a, b); } v[i] = {a, b}; if(p == q) { answer_c += b - a; /// Cost = distance } else { answer_c++; /// The bridge cost cnt_left++; sum_left += a + b; events[++ind] = {a, 0, i}; events[++ind] = {b + 1, 1, i}; } } sort(events + 1, events + ind + 1, cmp); int i = 1; answer = sum_left; while(i <= ind) { int j = i; while(j <= ind && events[i].x == events[j].x) { auto [x, type, pos] = events[j]; auto [a, b] = v[pos]; if(!type) { /// left erasing cnt_left--; sum_left -= a + b; /// inside adding sum_inside += b - a; } else { /// inside erasing sum_inside -= b - a; /// right adding cnt_right++; sum_right += a + b; } j++; } answer = min(answer, sum_left - 2LL * cnt_left * events[i].x + sum_inside + 2LL * cnt_right * events[i].x - sum_right); i = j; } cout << answer + answer_c << '\n'; return 0; }