#include <bits/stdc++.h> #define ll long long using namespace std; const int NMAX = 1e5; const int INF = 2e9; const ll INFLL = 1e18; int k, n, ind; ll left_sum, right_sum, answer, answer_c; pair<int, int> v[NMAX + 1]; multiset<int> left_s, right_s; ll pref_cost[NMAX + 5], suf_cost[NMAX + 1]; bool cmp(const pair<int, int>& a, const pair<int, int>& b) { return a.first + a.second < b.first + b.second; } void insert_s(int x) { int median = (left_s.empty() ? INF : *prev(left_s.end())); if(x <= median) { left_s.insert(x); left_sum += x; if((int) left_s.size() - (int) right_s.size() > 1) { right_s.insert(*prev(left_s.end())); right_sum += *prev(left_s.end()); left_sum -= *prev(left_s.end()); left_s.erase(prev(left_s.end())); } } else { right_s.insert(x); right_sum += x; if((int) right_s.size() - (int) left_s.size() > 0) { left_s.insert(*right_s.begin()); left_sum += *right_s.begin(); right_sum -= *right_s.begin(); right_s.erase(right_s.begin()); } } } void clear_s() { left_s.clear(); right_s.clear(); left_sum = right_sum = 0; } 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); } if(p == q) { answer_c += b - a; } else { v[++ind] = {a, b}; } } answer_c += ind; sort(v + 1, v + ind + 1, cmp); for(int i = 1; i <= ind; i++) { insert_s(v[i].first); insert_s(v[i].second); pref_cost[i] = right_sum - left_sum; } clear_s(); for(int i = ind; i >= 1; i--) { insert_s(v[i].first); insert_s(v[i].second); suf_cost[i] = right_sum - left_sum; } if(k == 1) { answer = pref_cost[ind]; } else { answer = INFLL; for(int i = 1; i < n; i++) { answer = min(answer, pref_cost[i] + suf_cost[i + 1]); } } cout << answer + answer_c << '\n'; return 0; }