#include <bits//stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll long long #define ld long double #define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1)) #define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1)) #define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1)) #define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1)) #define iloop_(m, h, g) for (auto i = m; i != h; i += g) #define jloop_(m, h, g) for (auto j = m; j != h; j += g) #define kloop_(m, h, g) for (auto k = m; k != h; k += g) #define lloop_(m, h, g) for (auto l = m; l != h; l += g) #define getchar_unlocked _getchar_nolock // comment before submission #define pll pair<ll, ll> #define plll pair<ll, pll> #define pllll pair<pll, pll> #define vll vector<ll> #define qll queue<ll> #define dll deque<ll> #define pqll priority_queue<ll> #define gll greater<ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll m, n; cin >> m >> n; char c[n], d[n]; ll a[n], b[n]; iloop(0, n) cin >> c[i] >> a[i] >> d[i] >> b[i]; if (m == 1) { vector<ll> v; ll cans = 0; iloop(0, n) if (c[i] != d[i]) {v.push_back(a[i]); v.push_back(b[i]); cans++;} if (v.size()) sort(v.begin(), v.end()); ll val = (v.size() ? v[v.size()/2] : 0); iloop(0, n) { if (c[i] == d[i]) cans += abs(a[i]-b[i]); else cans += abs(a[i]-val) + abs(b[i]-val); } cout << cans; } else { vector<pair<ll, pll>> cross; ll ans = 0; iloop(0, n) { if (c[i] == d[i]) ans += abs(a[i]-b[i]); else cross.push_back({a[i]+b[i], {a[i], b[i]}}); } sort(cross.begin(), cross.end()); ll m = cross.size(); ll pf[m + 1], sf[m + 1], tmp[m]; priority_queue<ll> pq; priority_queue<ll, vector<ll>, greater<ll>> pq_; pf[0] = 0; iloop(0, m) { pq.push(cross[i].second.first); pq.push(cross[i].second.second); if (pq_.size()) {pq.push(pq_.top()); pq_.pop();} if (pq_.size()) {pq.push(pq_.top()); pq_.pop();} while (pq.size() > pq_.size()) {pq_.push(pq.top()); pq.pop();} tmp[i] = pq.top(); } priority_queue<ll, vector<ll>, greater<ll>> cq; priority_queue<ll> cq_; ll cb = 0, cf = 0, cbc = 0, cfc = 0; iloop(0, m) { if (cross[i].second.first > tmp[i]) {cf += cross[i].second.first; cfc++; cq.push(cross[i].second.first);} else {cb += cross[i].second.first; cbc++; cq_.push(cross[i].second.first);} if (cross[i].second.second > tmp[i]) {cf += cross[i].second.second; cfc++; cq.push(cross[i].second.second);} else {cb += cross[i].second.second; cbc++; cq_.push(cross[i].second.second);} while (cq.size() && cq.top() < tmp[i]) {cfc--; cbc++; cf -= cq.top(); cb += cq.top(); cq_.push(cq.top()); cq.pop();} while (cq_.size() && cq_.top() > tmp[i]) {cfc++; cbc--; cf += cq_.top(); cb -= cq_.top(); cq.push(cq_.top()); cq_.pop();} pf[i+1] = cf - cfc*tmp[i] + cbc*tmp[i] - cb; } while (pq.size()) pq.pop(); while (pq_.size()) pq_.pop(); sf[m] = 0; iloop(m-1, -1) { pq.push(cross[i].second.first); pq.push(cross[i].second.second); if (pq_.size()) {pq.push(pq_.top()); pq_.pop();} if (pq_.size()) {pq.push(pq_.top()); pq_.pop();} while (pq.size() > pq_.size()) {pq_.push(pq.top()); pq.pop();} tmp[i] = pq.top(); } cb = 0, cf = 0, cbc = 0, cfc = 0; priority_queue<ll> dq; priority_queue<ll, vector<ll>, greater<ll>> dq_; iloop(m-1, -1) { //cout << tmp[i] << ":" << cross[i].second.first << "," << cross[i].second.second << "\n"; if (cross[i].second.first > tmp[i]) {cf += cross[i].second.first; cfc++; dq_.push(cross[i].second.first);} else {cb += cross[i].second.first; cbc++; dq.push(cross[i].second.first);} if (cross[i].second.second > tmp[i]) {cf += cross[i].second.second; cfc++; dq_.push(cross[i].second.second);} else {cb += cross[i].second.second; cbc++; dq.push(cross[i].second.second);} while (dq.size() && dq.top() > tmp[i]) {cbc--; cfc++; cb -= dq.top(); cf += dq.top(); dq_.push(dq.top()); dq.pop();} while (dq_.size() && dq_.top() < tmp[i]) {cbc++; cfc--; cb += dq_.top(); cf -= dq_.top(); dq.push(dq_.top()); dq_.pop();} sf[i] = cf - cfc*tmp[i] + cbc*tmp[i] - cb; } //iloop(0, m+1) cout << pf[i] << "," << sf[i] << "\n"; ll cmin = INF; iloop(0, m+1) cmin = min(cmin, pf[i] + sf[i]); cout << ans + cmin + m; } }