#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define el '\n'
const int maxN = 2005;
const int maxM = 205;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e18;
const int NEG_INF = -1e18;
const int MAX_DAYS = 1000;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int n, m, k, q, p, x, l;
// string S, T;
int S;
int dist[maxN][maxN], min_dist[maxN][maxN];
int par[maxN], deg[maxN], color[maxN];
bool visited[maxN];
int yard[maxN];
vector<pii> g[maxN], g_per[maxN];
string grid[maxN];
struct Citizen {
int id;
int st, ed;
};
bool cmpCitizen(Citizen a, Citizen b){
return (a.st + a.ed) < (b.st + b.ed);
}
// Prefix sum : S[i]
// => sum = S[i] - S[j-1]; len = i - (j-1);
// a <= len <= b
// i - b <= j - 1 <= i - a
vector<Citizen> Citizens;
struct MedianTracker {
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
int sumL = 0;
int sumR = 0;
void add(int x){
if(max_heap.empty() || x <= max_heap.top()){
max_heap.push(x);
sumL += x;
} else {
min_heap.push(x);
sumR += x;
}
while(max_heap.size() > min_heap.size() + 1){
int x = max_heap.top(); max_heap.pop();
min_heap.push(x);
sumR += x;
sumL -= x;
}
while(max_heap.size() < min_heap.size()) {
int x = min_heap.top(); min_heap.pop();
max_heap.push(x);
sumL += x;
sumR -= x;
}
}
int getCost(){
int median = max_heap.top();
int costL = median * max_heap.size() - sumL;
int costR = sumR - median * min_heap.size();
return costL + costR;
}
};
int solveK1(){
vector<int> v;
for(auto c : Citizens){
v.push_back(c.st);
v.push_back(c.ed);
}
sort(all(v));
int median = v[v.size()/2];
int ans = 0;
for(int i = 0; i < v.size(); i++){
ans += abs(v[i] - median);
}
return ans;
}
int solveK2(){
int m = Citizens.size();
if (m == 0) return 0;
MedianTracker mtl;
vector<int> costL(m+5, 0);
for(int i = 0; i < m; i++){
mtl.add(Citizens[i].st);
mtl.add(Citizens[i].ed);
costL[i] = mtl.getCost();
}
MedianTracker mtr;
vector<int> costR(m+5, 0);
for(int i = m - 1; i >= 0; i--){
mtr.add(Citizens[i].st);
mtr.add(Citizens[i].ed);
costR[i] = mtr.getCost();
}
int ans = INF;
for(int i = 0; i < m; i++){
ans = min(ans, costL[i] + costR[i+1]);
}
return ans;
}
void run_test() {
cin >> k >> n;
int baseCost = 0;
for(int i = 1; i <= n; i++){
int st, ed;
char P, Q;
cin >> P >> st >> Q >> ed;
if(P == Q) baseCost += abs(st-ed);
else Citizens.push_back({i,st,ed});
}
baseCost += Citizens.size();
sort(all(Citizens), cmpCitizen);
int ans;
if(k == 1)
ans = solveK1();
else
ans = solveK2();
cout << ans + baseCost;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("hayfeast.in", "r", stdin);
// freopen("hayfeast.out", "w", stdout);
int test = 1;
// cin >> test;
while (test-- > 0)
{
run_test();
}
}
