#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define pb push_back #define ff first #define ss second #define ii pair<int, int> #define vi vector<int> #define vii vector<pair<int, int>> #define yes cout << "YES\n" #define no cout << "NO\n" #define mii map<int, int> #define rep(i, a, b) for (int i = a; i <= b; i++) #define all(a, len) (a) + 1, (a) + len + 1 #define vall(a) (a).begin(), a.end() #define _READ(name) freopen(name, "r", stdin) #define _WRITE(name) freopen(name, "w", stdout) const int INF = 4e18; const int MOD = 1e9 + 7; int k, n; multiset<int> ms1, ms2; int suml, sumr; void insert(int x) { if (ms2.size() && *ms2.begin() < x) { ms2.insert(x); sumr += x; } else { ms1.insert(x); suml += x; } if (ms1.size() > ms2.size() + 1) { int last = *ms1.rbegin(); ms2.insert(last); ms1.erase(ms1.find(last)); suml -= last; sumr += last; } if (ms2.size() > ms1.size()) { int first = *ms2.begin(); ms1.insert(first); ms2.erase(ms2.find(first)); sumr -= first; suml += first; } } int pref[100005]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> k >> n; vii a; int same = 0; while (n--) { char p, q; int s, t; cin >> p >> s >> q >> t; if (p == q) { same += abs(s-t); } else { a.pb({s, t}); } } n = a.size()-1; same += n + 1; sort(a.begin(), a.end(), [](ii x, ii y) { return x.ff + x.ss < y.ff + y.ss; }); for (int i = 0; i <= n; i++) { insert(a[i].ff); insert(a[i].ss); pref[i] = sumr - suml; } if (k == 1) { cout << pref[n] + same; return 0; } ms1.clear(); ms2.clear(); int ans = pref[n]; suml = sumr = 0; for (int i = n; i > 0; i--) { insert(a[i].ff); insert(a[i].ss); ans = min(ans, sumr - suml + pref[i-1]); } cout << ans + same; return 0; }