#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1.77013e15;
mt19937 rng(time(0));
struct abssm {
abssm() {
root = new node();
root->prior = rng();
root->x = -INF;
root->slope = root->y = 0;
}
ll find_opty() {
node* nd = find_nonneg(root);
return nd->y;
}
void addabs(ll x) {
auto [l, r] = split_x(root, x);
node* nd = find_first(r);
node* pv = find_last(l);
if (!nd || nd->x != x) {
node* nd0 = new node();
nd0->prior = rng();
nd0->x = x;
nd0->y = pv->y + (x - pv->x) * pv->slope;
nd0->slope = pv->slope;
r = merge(nd0, r);
}
r->lazy_slope += 1;
r->lazy_y += r->x - x;
l->lazy_slope += -1;
l->lazy_y += x - l->x;
root = merge(l, r);
}
void output() {
output(root);
}
private:
struct node {
node* l = nullptr;
node* r = nullptr;
ll prior;
ll x;
ll y;
ll slope;
ll lazy_slope = 0;
ll lazy_y = 0;
};
void output(node* nd) {
if (!nd)
return;
push(nd);
output(nd->l);
cout << "(" << nd->x << ' ' << nd->y << ' ' << nd->slope << ") ";
output(nd->r);
}
node* root;
void push(node* nd) {
if (nd->l) {
nd->l->lazy_slope += nd->lazy_slope;
nd->l->lazy_y += (nd->l->x - nd->x) * nd->lazy_slope + nd->lazy_y;
}
if (nd->r) {
nd->r->lazy_slope += nd->lazy_slope;
nd->r->lazy_y += (nd->r->x - nd->x) * nd->lazy_slope + nd->lazy_y;
}
nd->y += nd->lazy_y;
nd->lazy_y = 0;
nd->slope += nd->lazy_slope;
nd->lazy_slope = 0;
}
pair<node*, node*> split_x(node* nd, ll x) {
if (!nd)
return {nullptr, nullptr};
push(nd);
if (x <= nd->x) {
auto [l, r] = split_x(nd->l, x);
nd->l = r;
return {l, nd};
} else {
auto [l, r] = split_x(nd->r, x);
nd->r = l;
return {nd, r};
}
}
node* merge(node* l, node* r) {
if (!l && !r)
return nullptr;
if (!l) {
push(r);
return r;
}
if (!r) {
push(l);
return l;
}
push(l);
push(r);
if (l->prior > r->prior) {
node* lr = merge(l->r, r);
l->r = lr;
return l;
} else {
node* rl = merge(l, r->l);
r->l = rl;
return r;
}
}
node* find_nonneg(node* nd) {
if (!nd)
return nullptr;
push(nd);
if (nd->slope < 0)
return find_nonneg(nd->r);
node* l = find_nonneg(nd->l);
if (l)
return l;
if (nd->slope >= 0)
return nd;
return nullptr;
}
node* find_first(node* nd) {
if (!nd)
return nullptr;
push(nd);
if (!nd->l)
return nd;
return find_first(nd->l);
}
node* find_last(node* nd) {
if (!nd)
return nullptr;
push(nd);
if (!nd->r)
return nd;
return find_last(nd->r);
}
};
const ll MAXN = 100003;
pair<ll, ll> sg[MAXN];
ll pref_ans[MAXN];
ll suf_ans[MAXN];
signed main() {
ll k, n = 0;
ll n0;
cin >> k >> n0;
ll addans = 0;
for (ll i = 0; i < n0; ++i) {
char c1, c2;
ll d1, d2;
cin >> c1 >> d1 >> c2 >> d2;
if (d1 > d2)
swap(d1, d2);
d1 *= 2;
d2 *= 2;
if (c1 == c2) {
addans += d2 - d1;
} else {
sg[n] = {(d1 + d2) / 2, (d2 - d1) / 2};
++n;
}
}
sort(sg, sg + n);
//for (ll i = 0; i < n; ++i)
//cout << "(" << sg[i].first - sg[i].second << ' ' << sg[i].first + sg[i].second << ") ";
//cout << endl;
abssm t;
for (ll i = 0; i < n; ++i) {
t.addabs(sg[i].first - sg[i].second);
t.addabs(sg[i].first + sg[i].second);
//t.output();
//cout << endl;
pref_ans[i] = t.find_opty();
}
abssm t0;
for (ll i = n - 1; i >= 0; --i) {
t0.addabs(sg[i].first - sg[i].second);
t0.addabs(sg[i].first + sg[i].second);
suf_ans[i] = t0.find_opty();
}
//for (ll i = 0; i < n; ++i) {
//cout << pref_ans[i] << ' ' << suf_ans[i] << endl;
//}
if (k == 1) {
cout << (pref_ans[n - 1] + addans) / 2 + n << endl;
} else {
ll ans = suf_ans[0];
for (ll i = 0; i < n; ++i) {
ans = min(ans, pref_ans[i] + suf_ans[i + 1]);
}
cout << (ans + addans) / 2 + n << endl;
}
}
