//#pragma warning( disable : 4996 )
#include <bits/stdc++.h>
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
int N, K, temp1, temp2;
char tmp1, tmp2;
const int INTMAX = 2147483647;
int main()
{
/*
string problemName = "";
ifstream fin(problemName + ".in");
ofstream fout(problemName + ".out");
*/
ios::sync_with_stdio(0);
cin.tie(0);
cin >> K >> N;
if (K == 1) {
vector<pair<long long int, int>> significant;
long long int sum = 0;
int intervalnum = 0;
long long int starting;
long long int ending;
long long int curmin = INTMAX;
long long int cursum = 0;
for (int i = 0; i < N; i++) {
cin >> tmp1 >> temp1 >> tmp2 >> temp2;
if (tmp1 == tmp2) {
sum += abs(temp1 - temp2);
}
else {
intervalnum++;
if (temp1 > temp2) {
swap(temp1, temp2);
}
sum += (1 + temp2 - temp1);
significant.push_back({ temp1, 0 });
significant.push_back({ temp2, 1 });
}
}
sort(significant.begin(), significant.end());
for (pair<int, int> i : significant) {
if (!i.second) {
cursum += (2 * (i.first - significant[0].first));
}
}
ending = 0;
starting = intervalnum - 1;
curmin = cursum;
for (int i = 1; i < 2 * intervalnum; i++) {
if (significant[i].first != significant[i - 1].first) {
cursum += 2 * (significant[i].first - significant[i - 1].first) * (ending - starting);
curmin = min(cursum, curmin);
}
if (significant[i].second) {
ending++;
}
else {
starting--;
}
}
curmin = min(curmin, cursum);
cout << curmin + sum;
}
else {
long long int sum = 0;
multiset<int>::iterator lmedian;
multiset<int>::iterator rmedian;
long long int cursumleft = 0;
long long int cursumright = 0;
long long int curmin = INTMAX;
int intervalnum = 0;
vector<pair<int, pair<int, int>>> intervals;
multiset<int> significantleft;
multiset<int> significantright;
for (int i = 0; i < N; i++) {
cin >> tmp1 >> temp1 >> tmp2 >> temp2;
if (tmp1 == tmp2) {
sum += abs(temp2 - temp1);
}
else {
sum++;
intervalnum++;
if (temp1 > temp2) {
swap(temp1, temp2);
}
intervals.push_back({ temp1 + temp2, {temp1, temp2} });
significantright.insert(temp1);
significantright.insert(temp2);
}
}
sort(intervals.begin(), intervals.end());
rmedian = next(significantright.begin(), intervalnum);
for (const int& i : significantright) {
cursumright += abs(i - *rmedian);
}
curmin = cursumright;
temp1 = intervals[0].second.first;
temp2 = intervals[0].second.second;
significantleft.insert(temp1);
significantleft.insert(temp2);
significantright.erase(significantright.lower_bound(temp1));
significantright.erase(significantright.lower_bound(temp2));
lmedian = next(significantright.begin(), 1);
cursumleft += (temp2 - temp1);
cursumright -= (abs(*rmedian - temp2) + abs(*rmedian - temp1));
if (temp2 <= *rmedian) {
rmedian++;
}
//curmin = min(curmin, cursumleft + cursumright);
for (int i = 1; i < floor(intervalnum / 2); i++) {
temp1 = intervals[i].second.first;
temp2 = intervals[i].second.second;
significantleft.insert(temp1);
significantleft.insert(temp2);
significantright.erase(significantright.lower_bound(temp1));
significantright.erase(significantright.lower_bound(temp2));
cursumleft += (abs(*lmedian - temp2) + abs(*lmedian - temp1));
if (temp1 >= *lmedian) {
lmedian++;
}
cursumright -= (abs(*rmedian - temp2) + abs(*rmedian - temp1));
if (temp2 < *rmedian) {
rmedian++;
}
//curmin = min(curmin, cursumleft + cursumright);
}
cout << curmin + sum;
}
}
