///
/// ♪ Let the voice of love take you higher! ♪
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;
ll inf = 1e9+100;
const int N = 100010;
char c1[N], c2[N];
ll a1[N], a2[N];
int k, n;
ll get(int x, int y)
{
ll ans = 0;
Loop(i,0,n)
{
if(c1[i] == c2[i]) ans += abs(a2[i]-a1[i]);
else ans += 1+min(abs(a1[i]-x)+abs(a2[i]-x), abs(a1[i]-y)+abs(a2[i]-y));
}
return ans;
}
ll bin21i(ll x)
{
ll l = 0, r = inf;
while(l < r)
{
ll m = (l+r)/2;
ll v1 = get(x-m,x+m);
ll v2 = get(x-m-1,x+m+1);
if(v1 < v2) r = m;
else l = m+1;
}
return get(x-l,x+l);
}
ll bin21h(ll x)
{
ll l = 0, r = inf;
while(l < r)
{
ll m = (l+r)/2;
ll v1 = get(x-m,x+m+1);
ll v2 = get(x-m-1,x+m+2);
if(v1 < v2) r = m;
else l = m+1;
}
return get(x-l,x+l+1);
}
ll bin21(ll x){return (x&1)?bin21h(x/2):bin21i(x/2);}
ll bin22()
{
ll l = 2*inf, r = 0;
Loop(i,0,n)
{
if(c1[i] != c2[i])
l = min(l, a1[i]+a2[i]),
r = max(r, a1[i]+a2[i]);
}
while(l < r)
{
ll m = (l+r)/2;
ll v1 = bin21(m);
ll v2 = bin21(m+1);
if(v1 < v2) r = m;
else l = m+1;
}
return bin21(l);
}
ll bin11()
{
ll l = 0, r = inf;
while(l < r)
{
ll m = (l+r)/2;
ll v1 = get(m,-inf);
ll v2 = get(m+1,-inf);
if(v1 < v2) r = m;
else l = m+1;
}
return get(l,-inf);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
#ifndef EVAL
freopen("in.txt", "r", stdin);
#endif
cin >> k >> n;
Loop(i,0,n)
{
cin >> c1[i] >> a1[i];
cin >> c2[i] >> a2[i];
}
cout << (k==2?bin22():bin11()) << '\n';
}
