#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
vector<ll> a, b, pa, pb;
ll query(ll x, ll y)
{
ll idx = upper_bound(b.begin(), b.end(), x) - b.begin();
ll ans = idx * x - pb[idx];
idx = upper_bound(a.begin(), a.end(), y) - a.begin();
ans += pa.back() - pa[idx] - (a.size() - idx) * y;
return ans;
}
signed main()
{
int k, n;
cin >> k >> n;
ll ans = 0;
vector<pair<int,int> > p;
for(int i = 0; i < n; i ++)
{
char P, Q;
int s, t;
cin >> P >> s >> Q >> t;
if(t < s) swap(s, t);
if(P == Q)
ans += t - s;
else
{
a.push_back(s);
b.push_back(t);
p.push_back({s, t});
}
}
pa.resize(1 + a.size());
pb.resize(1 + b.size());
sort(a.begin(), a.end());
sort(b.begin(), b.end());
pa[0] = pb[0] = 0;
for(int i = 0; i < a.size(); i++)
{
pa[i + 1] = pa[i] + a[i];
pb[i + 1] = pb[i] + b[i];
}
ans += p.size();
if(k == 1)
{
vector<ll> v;
for(auto [x, y] : p)
{
v.push_back(x);
v.push_back(y);
}
sort(v.begin(), v.end());
ll testans = 1e18 * (!v.empty()), suf = 0, sz = v.size();
for(ll i : v) suf += i;
ll prf = 0, cnt = 0;
for(ll i : v)
{
testans = min(testans, cnt * i - prf + suf - (sz - cnt) * i);
prf += i;
suf -= i;
cnt++;
}
ans += testans;
}
else
{
ll testans = 1e18 * (!p.empty());
vector<ll> v;
for(auto [x, y] : p)
v.push_back(y), v.push_back(x), ans += y - x;
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
int cnt = 0;
map<int, vector<pair<int, int> > > mp;
for(auto [x, y] : p)
mp[y].push_back({x, cnt++});
for(int i = 0; i < v.size(); i ++)
{
set<pair<int, int> > st;
ll cost = 0, costp = 0;
for(int j = i; j < v.size(); j++)
{
ll temp = query(v[i], v[j]);
if(st.size())
cost += 1ll * st.size() * (v[j] - v[j - 1]);
while(st.size() && st.begin()->first <= v[j])
{
int idx = st.begin()->second;
costp += p[i].first - v[i];
cost -= v[j] - p[i].second;
st.erase(st.begin());
}
if(j - 1 >= i && !mp[v[j - 1]].empty())
{
for(auto [s, idx] : mp[v[j - 1]])
if(v[i] < s)
{
if(s - v[i] <= v[j] - v[j - 1])
costp += s - v[i];
else
{
cost += v[j] - v[j - 1];
st.insert({v[j - 1] + s - v[i], idx});
}
}
}
testans = min(testans, temp + cost + costp);
}
}
ans += testans;
}
cout << ans << endl;
return 0;
}
