#include <bits/stdc++.h>
/*
Chang ki si xuyen man dem
Di lac vao trong giac mong
*/
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;
int k, n;
struct item {
char p, q;
int s, t;
};
item a[N], b[N];
int sz, S;
vector <int> comp;
bool cmp(item x, item y) {
return x.s + x.t < y.s + y.t;
}
struct ST {
pii st[8 * N]; // fi la so luong, se la tong
// int tree[8 * N];
void update(int i, int l, int r, int pos, int val, int tt) {
if (l == r) {
st[i].fi += val;
st[i].se += val * comp[pos - 1];
// tree[i] += tt;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(2 * i, l, mid, pos, val, tt);
else update(2 * i + 1, mid + 1, r, pos, val, tt);
st[i].fi = st[2 * i].fi + st[2 * i + 1].fi;
st[i].se = st[2 * i].se + st[2 * i + 1].se;
// tree[i] = tree[2 * i] + tree[2 * i + 1];
}
int get_med(int i, int l, int r, int val) {
if (l > r) return 0;
if (l == r) return l;
if (st[i].fi < val) return 0;
int mid = (l + r) / 2;
int ans = 0;
// cout << i << ' ' << l << ' ' << r << ' ' << val << ' ' << mid << ' ' << st[2 * i].fi << ' ' << st[2 * i + 1].fi << '\n';
if (st[2 * i].fi >= val) ans = get_med(2 * i, l, mid, val);
if (!ans) ans = get_med(2 * i + 1, mid + 1, r, val - st[2 * i].fi);
return ans;
}
pii get1(int i, int l, int r, int u, int v) {
if (u > r || v < l) return make_pair(0, 0);
if (u <= l && r <= v) return st[i];
int mid = (l + r) / 2;
pii valL = get1(2 * i, l, mid, u, v);
pii valR = get1(2 * i + 1, mid + 1, r, u, v);
return make_pair(valL.fi + valR.fi, valL.se + valR.se);
}
// int get2(int i, int l, int r, int u, int v) {
// if (u > r || v < l) return 0;
// if (u <= l && r <= v) return tree[i];
// int mid = (l + r) / 2;
// return get2(2 * i, l, mid, u, v) + get2(2 * i + 1, mid + 1, r, u, v);
// }
} st1, st2;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> k >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i].p >> a[i].s >> a[i].q >> a[i].t;
if (a[i].p != a[i].q) {
comp.push_back(a[i].s);
comp.push_back(a[i].t);
b[++sz] = a[i];
}
else {
ans += abs(a[i].t - a[i].s);
}
}
if (sz == 0) {
cout << ans << '\n';
return 0;
}
// for (int i = 1; i <= sz; i++) {
// cout << b[i].s << ' ' << b[i].t << '\n';
// }
sort(b + 1, b + sz + 1, cmp);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
// for (auto x : comp) cout << x << ' ';
// cout << '\n';
S = comp.size();
// cout << "size: " << S << '\n';
for (int i = 1; i <= sz; i++) {
b[i].s = lower_bound(comp.begin(), comp.end(), b[i].s) - comp.begin() + 1;
b[i].t = lower_bound(comp.begin(), comp.end(), b[i].t) - comp.begin() + 1;
}
for (int i = 1; i <= sz; i++) {
st2.update(1, 1, S, b[i].s, 1, 1);
st2.update(1, 1, S, b[i].t, 1, 0);
}
if (k == 1) {
auto p = st2.get_med(1, 1, S, sz);
// cout << p << ' ' << comp[p - 1] << '\n';
pii valL = st2.get1(1, 1, S, 1, p);
pii valR = st2.get1(1, 1, S, p + 1, S);
// cout << valL.se << ' ' << valR.se << '\n';
ans += comp[p - 1] * valL.fi - valL.se;
ans += valR.se - comp[p - 1] * valR.fi;
ans += sz;
cout << ans << '\n';
}
else {
int res = inf;
for (int i = 1; i < sz; i++) {
// cout << "value: " << b[i].s << ' ' << b[i].t << '\n';
int tmp = ans;
st1.update(1, 1, S, b[i].s, 1, 1);
st1.update(1, 1, S, b[i].t, 1, 0);
st2.update(1, 1, S, b[i].s, -1, -1);
st2.update(1, 1, S, b[i].t, -1, 0);
{
// if (i == 3) {
// cout << "now: " << '\n';
// }
auto p = st1.get_med(1, 1, S, i);
// if (i == 3) {
// cout << "at: " << '\n';
// cout << p << ' ' << comp[p - 1] << '\n';
// }
pii valL = st1.get1(1, 1, S, 1, p);
pii valR = st1.get1(1, 1, S, p + 1, S);
tmp += comp[p - 1] * valL.fi - valL.se;
tmp += valR.se - comp[p - 1] * valR.fi;
// int add = st1.get2(1, 1, S, 1, S);
int add = i;
tmp += add;
}
{
auto p = st2.get_med(1, 1, S, (sz - i));
pii valL = st2.get1(1, 1, S, 1, p);
pii valR = st2.get1(1, 1, S, p + 1, S);
tmp += comp[p - 1] * valL.fi - valL.se;
tmp += valR.se - comp[p - 1] * valR.fi;
// int add = st2.get2(1, 1, S, 1, S);
int add = (sz - i);
tmp += add;
}
// cout << i << ' ' << tmp << '\n';
res = min(res, tmp);
}
cout << res << '\n';
}
return 0;
}
