#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k, n;
ll s, t, numLeft, numRight, distFrom0;
char p, q;
vector<pair<ll, ll> > events;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n;
ll minSum = 0;
numLeft = numRight = distFrom0 = 0;
if (k == 1)
{
for (int i = 0; i < n; i++)
{
cin >> p >> s >> q >> t;
if (p == q)
{
minSum += abs(t - s);
}
else
{
minSum += 1 + abs(t - s);
ll b = max(t, s);
ll a = min(t, s);
events.push_back({a, -1});
events.push_back({b, 1});
numRight++;
distFrom0 += a;
}
}
//cout << "Min sum is " << minSum << "\n";
//cout << "Initial dist: " << distFrom0 << "\n";
sort(events.begin(), events.end());
ll prevLocation = 0;
ll finAns = 1000000000000000;
if (events.size() == 0)
{
finAns = minSum;
}
for (int i = 0; i < events.size(); i++)
{
ll currLocation = events[i].first;
distFrom0 -= numRight * (currLocation - prevLocation);
distFrom0 += numLeft * (currLocation - prevLocation);
if (events[i].second == -1)
{
numRight--;
}
else
{
numLeft++;
}
finAns = min(finAns, minSum + 2 * distFrom0);
//cout << "At location " << currLocation << " dist is " << distFrom0 << '\n';
prevLocation = currLocation;
}
cout << finAns << "\n";
return 0;
}
for (int i = 0; i < n; i++)
{
cin >> p >> s >> q >> t;
if (p == q)
{
minSum += abs(t - s);
}
else
{
minSum += 1 + abs(t - s);
ll b = max(t, s);
ll a = min(t, s);
events.push_back({a, b});
}
}
if(events.size() < 2) {
cout << minSum << "\n";
return 0;
}
//sort(events.begin(), events.end());
ll finAns = 1000000000000000;
for (int i = 0; i < events.size(); i++)
{
for (int j = i+1; j < events.size(); j++)
{
ll bri1 = events[i].first;
ll bri2 = events[j].first;
ll bridge1 = min(bri1, bri2);
ll bridge2 = max(bri1, bri2);
ll totAddOn = 0;
for (int k = 0; k < events.size(); k++)
{
if(events[k].second <= bridge1) {
totAddOn += 2 * (bridge1-events[k].second);
}
else if (events[k].first >= bridge2)
{
totAddOn += 2 * (events[k].first-bridge2);
}
else if (events[k].first > bridge1 and events[k].second < bridge2)
{
totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
}
}
finAns = min(finAns, minSum + totAddOn);
bri1 = events[i].second;
bri2 = events[j].first;
bridge1 = min(bri1, bri2);
bridge2 = max(bri1, bri2);
totAddOn = 0;
for (int k = 0; k < events.size(); k++)
{
if(events[k].second <= bridge1) {
totAddOn += 2 * (bridge1-events[k].second);
}
else if (events[k].first >= bridge2)
{
totAddOn += 2 * (events[k].first-bridge2);
}
else if (events[k].first > bridge1 and events[k].second < bridge2)
{
totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
}
}
finAns = min(finAns, minSum + totAddOn);
bri1 = events[i].first;
bri2 = events[j].second;
bridge1 = min(bri1, bri2);
bridge2 = max(bri1, bri2);
totAddOn = 0;
for (int k = 0; k < events.size(); k++)
{
if(events[k].second <= bridge1) {
totAddOn += 2 * (bridge1-events[k].second);
}
else if (events[k].first >= bridge2)
{
totAddOn += 2 * (events[k].first-bridge2);
}
else if (events[k].first > bridge1 and events[k].second < bridge2)
{
totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
}
}
finAns = min(finAns, minSum + totAddOn);
bri1 = events[i].second;
bri2 = events[j].second;
bridge1 = min(bri1, bri2);
bridge2 = max(bri1, bri2);
totAddOn = 0;
for (int k = 0; k < events.size(); k++)
{
if(events[k].second <= bridge1) {
totAddOn += 2 * (bridge1-events[k].second);
}
else if (events[k].first >= bridge2)
{
totAddOn += 2 * (events[k].first-bridge2);
}
else if (events[k].first > bridge1 and events[k].second < bridge2)
{
totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
}
}
finAns = min(finAns, minSum + totAddOn);
}
}
cout << finAns << "\n";
}
