#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
/**
* Author: Simon Lindholm
* Date: 2015-09-12
* License: CC0
* Source: me
* Description: When you need to dynamically allocate many objects and don't care about freeing them.
* "new X" otherwise has an overhead of something like 0.05us + 16 bytes per allocation.
* Status: tested
*/
#pragma once
// Either globally or in a single class:
static char buf[450 << 20];
void* operator new(size_t s) {
static size_t i = sizeof buf;
assert(s < i);
return (void*)&buf[i -= s];
}
void operator delete(void*) {}
using ll = long long;
using pii = pair <ll, ll>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const ll maxN = 1e6;
const ll inf = 1e9 + 1;
ll k, n;
ll suf[maxN], pre[maxN];
struct TNode{
TNode *l, *r;
ll val;
ll sum;
TNode (const ll &i, const ll &j) : l(nullptr), r(nullptr), val(i), sum(j){}
TNode (TNode* i, TNode* j){
l = i; r = j;
val = 0; sum = 0;
if (l){
val += l->val;
sum += l->sum;
}
if (r){
val += r->val;
sum += r->sum;
}
}
};
TNode* root[maxN];
void create_node(TNode* id){
if (!id->l) id->l = new TNode(0ll, 0ll);
if (!id->r) id->r = new TNode(0ll, 0ll);
}
TNode* update(TNode* id, ll i, ll l = 0, ll r = inf){
if (l == r) return new TNode(id->val + 1, id->sum + i);
ll m = (l + r) / 2;
create_node(id);
if (m >= i) return new TNode(update(id->l, i, l, m), id->r);
return new TNode(id->l, update(id->r, i, m + 1, r));
}
ll remainer;
ll get(TNode* left, TNode* right, ll k, ll l = 0, ll r = inf){
//finding the kth largest numbers from left -> right
if (l == r){
remainer = right->sum - left->sum - (l * k);
return l;
}
ll m = (l + r) / 2;
ll cntl = (left->l) ? left->l->val : 0;
ll cntr = (right->l) ? right->l->val : 0;
if (cntr - cntl < k) return get((left->r) ? left->r : left, (right->r) ? right->r : right, k - cntr + cntl, m + 1, r);
return get((left->l) ? left->l : left, (right->l) ? right->l : right, k, l, m);
}
ll getsum(TNode* left, TNode* right, ll i, ll j, ll l = 0, ll r = inf){
//get sum of all elements ranged between i and j from left to right
if (r < i || l > j) return 0;
if (i <= l && r <= j){
return right->sum - left->sum;
}
ll m = (l + r) / 2;
ll x = getsum((left->l) ? left->l : left, (right->l) ? right->l : right, i, j, l, m);
ll y = getsum((left->r) ? left->r : left, (right->r) ? right->r : right, i, j, m + 1, r);
return x + y;
}
void Init(){
ll ans = 0;
cin >> k >> n;
if (k == 1){
vector <ll> v;
for (ll i = 1; i <= n; ++i){
char p, q; ll s, t;
cin >> p >> s >> q >> t;
if (p != q){
++ans;
v.pb(s);
v.pb(t);
}
else{
ans += abs(s - t);
}
}
v.push_back(0);
sort(v.begin(), v.end());
ll m = v.size();
ll tem = LLONG_MAX;
for (ll i = 1; i < m; ++i){
pre[i] = pre[i - 1] + v[i];
}
for (ll i = m - 1; i > 0; --i){
suf[i] = suf[i + 1] + v[i];
}
for (ll i = 1; i < m; ++i){
tem = min(tem, v[i] * (i - 1) - pre[i - 1] + suf[i + 1] - v[i] * (m - i - 1));
}
if (m == 1) tem = 0;
cout << ans + tem;
return;
}
vector <pii> v;
for (ll i = 1; i <= n; ++i){
char p, q; ll s, t;
cin >> p >> s >> q >> t;
if (p != q){
++ans;
v.pb({s, t});
}
else ans += abs(s - t);
}
if (v.empty()){
cout << ans; return;
}
if (v.size() == 1){
cout << ans + abs(v[0].fi - v[0].se);
return;
}
sort(v.begin(), v.end(),[](const pii &i, const pii &j){
return (i.fi + i.se) / 2 < (j.fi + j.se) / 2;
});
root[0] = new TNode(0ll, 0ll);
for (ll i = 1; i <= v.size(); ++i){
pre[i] = pre[i - 1] + v[i - 1].fi + v[i - 1].se;
root[i] = update(root[i - 1], v[i - 1].fi);
root[i] = update(root[i], v[i - 1].se);
}
ll tem = LLONG_MAX;
for (ll i = 0; i < v.size() - 1; ++i){
ll x = get(root[0], root[i + 1], i + 1);
ll l = getsum(root[0], root[i + 1], 0, x) - remainer;
ll y = get(root[i + 1], root[v.size()], v.size() - i - 1);
ll r = getsum(root[i + 1], root[v.size()], 0, y) - remainer;
tem = min(tem, pre[i + 1] - 2 * l + pre[v.size()] - pre[i + 1] - 2 * r);
}
cout << tem + ans;
}
signed main(){
if (fopen(taskname".txt", "r")){
freopen(taskname".txt", "r", stdin);
freopen(taskname".out", "w", stdout);
}
faster
Init();
}
