#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, n;
int res = 0;
int m = 0;
vector<int> vc;
map<int, int> mp;
int c = 0;
struct TCitizen
{
char p;
int s;
char q;
int t;
} a[maxN];
map<int, int> nerf, origin;
void ReadInput()
{
cin >> k >> n;
int cnt = 0, cnt1 = 0;
for(int i=1; i<=n; i++)
{
char p, q;
int s, t;
cin >> p >> s >> q >> t;
// if(s == t) c++;
vc.pb((s + t) / 2);
if(p == q)
{
res += abs(s - t);
continue;
}
if(s == 0) cnt++;
else cnt1++;
vc.pb(s);
vc.pb(t);
if(s > t)
swap(s, t);
a[++m] = {p, s, q, t};
}
vector<int> vc;
for(int i=1; i<=m; i++)
{
vc.pb(a[i].s);
vc.pb(a[i].t);
vc.pb((a[i].s + a[i].t) / 2);
}
sort(vc.begin(), vc.end());
int p = 0;
for(int v : vc)
{
if(nerf[v]) continue;
nerf[v] = ++p;
origin[p] = v;
}
// cout << cnt << " " << cnt1;exit(0);
// cout << c;exit(0);
}
struct BIT
{
int n;
vector<int> bit;
BIT(int _n)
{
n = _n * 3;
bit.resize(n + 1);
}
void reset()
{
for(int i=1; i<=n; i++) bit[i] = 0;
}
void update(int pos, int val)
{
for(; pos <= n; pos += (pos & (-pos)))
bit[pos] += val;
}
int get(int pos)
{
int res = 0;
for(; pos; pos -= (pos & (-pos)))
res += bit[pos];
return res;
}
};
pair<int, int> bit[maxN];
void update(int pos, int val)
{
while(pos <= n * 3)
{
bit[pos].fi += val;
bit[pos].se++;
pos += (pos & (-pos));
}
}
pair<int, int> get(int pos)
{
pair<int, int> res;
while(pos)
{
res.fi += bit[pos].fi;
res.se += bit[pos].se;
pos -= (pos & (-pos));
}
return res;
}
pair<int, int> get_range(int l, int r)
{
pair<int, int> val1 = get(r), val2 = get(l - 1);
return {val1.fi - val2.fi, val1.se - val2.se};
}
void sub1()
{
sort(vc.begin(), vc.end());
vc.erase(unique(vc.begin(), vc.end()), vc.end());
sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
{
return p.s < q.s;
});
int p = 1;
int sum = 0;
for(int x : vc)
{
while(p <= m && a[p].s <= x)
{
sum += a[p].s;
p++;
}
mp[x] += x * (p - 1) - sum;
}
sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
{
return p.t < q.t;
});
p = 1;
sum = 0;
for(int x : vc)
{
while(p <= m && a[p].t <= x)
{
sum += a[p].t;
p++;
}
mp[x] += x * (p - 1) - sum;
}
reverse(vc.begin(), vc.end());
sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
{
return p.s > q.s;
});
p = 1;
sum = 0;
for(int x : vc)
{
while(p <= m && a[p].s >= x)
{
sum += a[p].s;
p++;
}
mp[x] += -(x * (p - 1) - sum);
}
sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
{
return p.t > q.t;
});
p = 1;
sum = 0;
for(int x : vc)
{
while(p <= m && a[p].t >= x)
{
sum += a[p].t;
p++;
}
mp[x] += -(x * (p - 1) - sum);
}
int _min = oo;
for(pair<int, int> v : mp)
_min = min(_min, v.se);
_min += m;
cout << res + _min;
}
pair<int, int> ans[maxN];
void sub2()
{
BIT bit1(n);
sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
{
return p.s + p.t < q.s + q.t;
});
for(int i=1; i<=m; i++)
{
bit1.update(nerf[a[i].s], 1);
bit1.update(nerf[a[i].t], 1);
int low = 1, high = n * 3, mid;
while(low <= high)
{
mid = (low + high) / 2;
int val = bit1.get(mid);
if(val >= i) high = mid - 1;
else low = mid + 1;
}
update(nerf[a[i].s], a[i].s);
update(nerf[a[i].t], a[i].t);
//cout << get_range(3, 3).fi;return;
pair<int, int> val1 = get_range(1, low);
ans[i].fi += origin[low] * val1.se - val1.fi;
pair<int, int> val2 = get_range(low, n * 3);
ans[i].fi += val2.fi - origin[low] * val2.se;
// cout << origin[mid] << '\n';
// cout << ans[i].fi << " ";
}
// return;
// return;
memset(bit, 0, sizeof bit);
bit1.reset();
for(int i=m; i>=1; i--)
{
bit1.update(nerf[a[i].s], 1);
bit1.update(nerf[a[i].t], 1);
int low = 1, high = n * 3, mid;
// cout << bit1.get(15);return;
while(low <= high)
{
mid = (low + high) / 2;
int val = bit1.get(mid);
if(val >= (m - i + 1)) high = mid - 1;
else low = mid + 1;
}
update(nerf[a[i].s], a[i].s);
update(nerf[a[i].t], a[i].t);
pair<int, int> val1 = get_range(1, low);
ans[i].se += origin[low] * val1.se - val1.fi;
pair<int, int> val2 = get_range(low, n * 3);
ans[i].se += val2.fi - origin[low] * val2.se;
// cout << ans[i].se << " ";
}
assert(m);
// return;
int _min = oo;
for(int i=0; i<=m; i++)
{
_min = min(_min, ans[i].fi + ans[i + 1].se);
}
cout << res + m + _min;
}
void Solve()
{
//cout << res;return;
if(!m)
{
cout << res;
return;
}
if(k == 1)
{
sub1();
}
else
sub2();
}
int32_t main()
{
//freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
