#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#ifdef KAZAR
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
#define eprintf(...) 0
#endif
using namespace std;
template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<int, int> ii;
const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;
inline int read(){int x;scanf(" %d",&x);return x;}
const int N = 3e5 + 100;
int n;
char p1[N], p2[N];
int x1[N], x2[N];
vector<int> xs;
inline int getid(int x){
return lower_bound(all(xs), x) - xs.begin();
}
int cnt_start[N], cnt_end[N];
ll lf[N], rg[N];
void pre(){
for(int i = 1; i <= n; i++){
if(p1[i] == p2[i])
continue;
cnt_start[getid(x1[i])]++;
cnt_end[getid(x2[i])]++;
}
int sz = xs.size();
{
ll sumx = 0;
int cnt = 0;
for(int i = 0; i < sz; i++){
lf[i] += (ll)xs[i] * cnt - sumx;
sumx += (ll)xs[i] * cnt_end[i];
cnt += cnt_end[i];
}
}{
ll sumx = 0;
int cnt = 0;
for(int i = sz - 1; i >= 0; i--){
rg[i] += sumx - (ll)xs[i] * cnt;
sumx += (ll)xs[i] * cnt_start[i];
cnt += cnt_start[i];
}
}
}
ll solve_one(){
ll res = longinf;
for(int i = 0; i < xs.size(); i++){
umin(res, lf[i] + rg[i]);
}
return res;
}
class fenwick{
public:
ll f[N];
void add(int x,ll v){
++x;
while(x < N){
f[x] += v;
x += x & -x;
}
}
ll get(int l,int r){
if(l > r)
return 0;
++l; ++r;
ll res = 0;
for(int i = r; i > 0; i -= i & -i)
res += f[i];
for(int i = l - 1; i > 0; i -= i & -i)
res -= f[i];
return res;
}
};
int L, R;
fenwick sumx1, sumx2, cnt;
void add(int x1,int x2,int c){
int id = getid(x1 + x2);
sumx1.add(id, x1 * c);
sumx2.add(id, x2 * c);
cnt.add(id, c);
}
int used[N];
vector<ii> vends[N];
vector<ii> vbegs[N];
void addL(int l,int r,int c){
for(int i = 0; i < vends[l].size(); i++){
int v = vends[l][i].first;
if(v > xs[r]) break;
used[vends[l][i].second] = c;
add(xs[l], v, c);
}
}
void addR(int l,int r,int c){
for(int i = 0; i < vbegs[r].size(); i++){
int v = vbegs[r][i].first;
if(v < xs[l]) break;
used[vbegs[r][i].second] = c;
add(v, xs[r], c);
}
}
ll ans = longinf;
void init(){
L = 0, R = 0;
addL(0, 0, +1);
}
void fix(int l,int r){
while(R < r) addR(L, ++R, +1);
while(R > r) addR(L, R--, -1);
while(L > l) addL(--L, R, +1);
while(L < l) addL(L++, R, -1);
}
int cL = 0, cR = 0;
ll calc(int l,int r){
int sz = xs.size();
ll res = lf[l] + rg[r];
int id = lower_bound(all(xs), xs[l] + xs[r]) - xs.begin() - 1;
ll cntL = cnt.get(0, id);
ll sumxL = sumx1.get(0, id);
res += sumxL - (ll)xs[l] * cntL;
ll cntR = cnt.get(id + 1, sz - 1);
ll sumxR = sumx2.get(id + 1, sz - 1);
res += (ll)xs[r] * cntR - sumxR;
return res;
}
void solve(int l,int r,int from,int to){
if(l > r)
return;
int m = (l + r) >> 1;
int st = max(m, from);
ll best = longinf;
int opt = 0;
for(int i = st; i <= to; i++){
fix(m, i);
assert(L == m);
assert(R == i);
cL = cR = 0;
ll t = calc(m, i);
if(t < best){
best = t;
opt = i;
}
}
if(best < ans){
ans = best;
}
solve(m + 1, r, opt, to);
solve(l, m - 1, from, opt);
}
ll solve_two(){
for(int i = 1; i <= n; i++){
if(p1[i] == p2[i])
continue;
vbegs[getid(x2[i])].push_back(ii(x1[i], i));
vends[getid(x1[i])].push_back(ii(x2[i], i));
}
int sz = xs.size();
for(int i = 0; i < sz; i++){
sort(all(vbegs[i]));
reverse(all(vbegs[i]));
sort(all(vends[i]));
}
memset(used, -1, sizeof used);
init();
solve(0, sz - 1, 0, sz - 1);
return ans;
}
int main(){
#ifdef KAZAR
freopen("f.input","r",stdin);
freopen("f.output","w",stdout);
freopen("error","w",stderr);
#endif
int k = read();
n = read();
ll more = 0;
for(int i = 1; i <= n; i++){
scanf(" %c %d %c %d", p1 + i, x1 + i, p2 + i, x2 + i);
if(x1[i] > x2[i])
swap(x1[i], x2[i]);
xs.push_back(x1[i]);
xs.push_back(x2[i]);
xs.push_back(x1[i] + x2[i]);
more += x2[i] - x1[i];
if(p1[i] != p2[i])
++more;
}
sort(all(xs));
xs.erase(unique(all(xs)), xs.end());
pre();
if(k == 1){
printf("%lld\n", solve_one() * 2 + more);
return 0;
}
printf("%lld\n", solve_two() * 2 + more);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwgKHgpLmVuZCgpCgojaWZkZWYgS0FaQVIKICAgICNkZWZpbmUgZXByaW50ZiguLi4pIGZwcmludGYoc3RkZXJyLF9fVkFfQVJHU19fKQojZWxzZQogICAgI2RlZmluZSBlcHJpbnRmKC4uLikgMAojZW5kaWYKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB1bWF4KFQgJmEsVCBiKXtpZihhPGIpIGEgPSBiIDsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB1bWluKFQgJmEsVCBiKXtpZihhPmIpIGEgPSBiIDsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgVCBhYnMoVCBhKXtyZXR1cm4gYT4wID8gYSA6IC1hO30KdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIFQgZ2NkKFQgYSxUIGIpe3JldHVybiBfX2djZChhLCBiKTt9CnRlbXBsYXRlPGNsYXNzIFQ+IGlubGluZSBUIGxjbShUIGEsVCBiKXtyZXR1cm4gYS9nY2QoYSxiKSpiO30KCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IGlpOwoKY29uc3QgaW50IGluZiA9IDFlOSArIDE0MzsKY29uc3QgbGwgbG9uZ2luZiA9IDFlMTggKyAxNDM7CgppbmxpbmUgaW50IHJlYWQoKXtpbnQgeDtzY2FuZigiICVkIiwmeCk7cmV0dXJuIHg7fQoKY29uc3QgaW50IE4gPSAzZTUgKyAxMDA7CgppbnQgbjsKY2hhciBwMVtOXSwgcDJbTl07CmludCB4MVtOXSwgeDJbTl07CnZlY3RvcjxpbnQ+IHhzOwoKaW5saW5lIGludCBnZXRpZChpbnQgeCl7CiAgICByZXR1cm4gbG93ZXJfYm91bmQoYWxsKHhzKSwgeCkgLSB4cy5iZWdpbigpOwp9CgppbnQgY250X3N0YXJ0W05dLCBjbnRfZW5kW05dOwpsbCBsZltOXSwgcmdbTl07Cgp2b2lkIHByZSgpewogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspewogICAgICAgIGlmKHAxW2ldID09IHAyW2ldKQogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICBjbnRfc3RhcnRbZ2V0aWQoeDFbaV0pXSsrOwogICAgICAgIGNudF9lbmRbZ2V0aWQoeDJbaV0pXSsrOwogICAgfQogICAgaW50IHN6ID0geHMuc2l6ZSgpOwogICAgewogICAgICAgIGxsIHN1bXggPSAwOwogICAgICAgIGludCBjbnQgPSAwOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgaSsrKXsKICAgICAgICAgICAgbGZbaV0gKz0gKGxsKXhzW2ldICogY250IC0gc3VteDsKICAgICAgICAgICAgc3VteCArPSAobGwpeHNbaV0gKiBjbnRfZW5kW2ldOwogICAgICAgICAgICBjbnQgKz0gY250X2VuZFtpXTsKICAgICAgICB9CiAgICB9ewogICAgICAgIGxsIHN1bXggPSAwOwogICAgICAgIGludCBjbnQgPSAwOwogICAgICAgIGZvcihpbnQgaSA9IHN6IC0gMTsgaSA+PSAwOyBpLS0pewogICAgICAgICAgICByZ1tpXSArPSBzdW14IC0gKGxsKXhzW2ldICogY250OwogICAgICAgICAgICBzdW14ICs9IChsbCl4c1tpXSAqIGNudF9zdGFydFtpXTsKICAgICAgICAgICAgY250ICs9IGNudF9zdGFydFtpXTsKICAgICAgICB9CiAgICB9Cn0KCmxsIHNvbHZlX29uZSgpewogICAgbGwgcmVzID0gbG9uZ2luZjsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCB4cy5zaXplKCk7IGkrKyl7CiAgICAgICAgdW1pbihyZXMsIGxmW2ldICsgcmdbaV0pOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoKY2xhc3MgZmVud2lja3sKcHVibGljOgogICAgbGwgZltOXTsKICAgIHZvaWQgYWRkKGludCB4LGxsIHYpewogICAgICAgICsreDsKICAgICAgICB3aGlsZSh4IDwgTil7CiAgICAgICAgICAgIGZbeF0gKz0gdjsKICAgICAgICAgICAgeCArPSB4ICYgLXg7CiAgICAgICAgfQogICAgfQogICAgbGwgZ2V0KGludCBsLGludCByKXsKICAgICAgICBpZihsID4gcikKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgKytsOyArK3I7CiAgICAgICAgbGwgcmVzID0gMDsKICAgICAgICBmb3IoaW50IGkgPSByOyBpID4gMDsgaSAtPSBpICYgLWkpCiAgICAgICAgICAgIHJlcyArPSBmW2ldOwogICAgICAgIGZvcihpbnQgaSA9IGwgLSAxOyBpID4gMDsgaSAtPSBpICYgLWkpCiAgICAgICAgICAgIHJlcyAtPSBmW2ldOwogICAgICAgIHJldHVybiByZXM7CiAgICB9Cn07CgppbnQgTCwgUjsKZmVud2ljayBzdW14MSwgc3VteDIsIGNudDsKCnZvaWQgYWRkKGludCB4MSxpbnQgeDIsaW50IGMpewogICAgaW50IGlkID0gZ2V0aWQoeDEgKyB4Mik7CiAgICBzdW14MS5hZGQoaWQsIHgxICogYyk7CiAgICBzdW14Mi5hZGQoaWQsIHgyICogYyk7CiAgICBjbnQuYWRkKGlkLCBjKTsKfQoKaW50IHVzZWRbTl07CnZlY3RvcjxpaT4gdmVuZHNbTl07CnZlY3RvcjxpaT4gdmJlZ3NbTl07Cgp2b2lkIGFkZEwoaW50IGwsaW50IHIsaW50IGMpewogICAgZm9yKGludCBpID0gMDsgaSA8IHZlbmRzW2xdLnNpemUoKTsgaSsrKXsKICAgICAgICBpbnQgdiA9IHZlbmRzW2xdW2ldLmZpcnN0OwogICAgICAgIGlmKHYgPiB4c1tyXSkgYnJlYWs7CiAgICAgICAgdXNlZFt2ZW5kc1tsXVtpXS5zZWNvbmRdID0gYzsKICAgICAgICBhZGQoeHNbbF0sIHYsIGMpOwogICAgfQp9Cgp2b2lkIGFkZFIoaW50IGwsaW50IHIsaW50IGMpewogICAgZm9yKGludCBpID0gMDsgaSA8IHZiZWdzW3JdLnNpemUoKTsgaSsrKXsKICAgICAgICBpbnQgdiA9IHZiZWdzW3JdW2ldLmZpcnN0OwogICAgICAgIGlmKHYgPCB4c1tsXSkgYnJlYWs7CiAgICAgICAgdXNlZFt2YmVnc1tyXVtpXS5zZWNvbmRdID0gYzsKICAgICAgICBhZGQodiwgeHNbcl0sIGMpOwogICAgfQp9CgpsbCBhbnMgPSBsb25naW5mOwoKdm9pZCBpbml0KCl7CiAgICBMID0gMCwgUiA9IDA7CiAgICBhZGRMKDAsIDAsICsxKTsKfQoKdm9pZCBmaXgoaW50IGwsaW50IHIpewogICAgd2hpbGUoUiA8IHIpIGFkZFIoTCwgKytSLCArMSk7CiAgICB3aGlsZShSID4gcikgYWRkUihMLCBSLS0sIC0xKTsKICAgIHdoaWxlKEwgPiBsKSBhZGRMKC0tTCwgUiwgKzEpOwogICAgd2hpbGUoTCA8IGwpIGFkZEwoTCsrLCBSLCAtMSk7Cn0KCmludCBjTCA9IDAsIGNSID0gMDsKCmxsIGNhbGMoaW50IGwsaW50IHIpewogICAgaW50IHN6ID0geHMuc2l6ZSgpOwogICAgbGwgcmVzID0gbGZbbF0gKyByZ1tyXTsKICAgIGludCBpZCA9IGxvd2VyX2JvdW5kKGFsbCh4cyksIHhzW2xdICsgeHNbcl0pIC0geHMuYmVnaW4oKSAtIDE7CiAgICBsbCBjbnRMID0gY250LmdldCgwLCBpZCk7CiAgICBsbCBzdW14TCA9IHN1bXgxLmdldCgwLCBpZCk7CiAgICByZXMgKz0gc3VteEwgLSAobGwpeHNbbF0gKiBjbnRMOwogICAgbGwgY250UiA9IGNudC5nZXQoaWQgKyAxLCBzeiAtIDEpOwogICAgbGwgc3VteFIgPSBzdW14Mi5nZXQoaWQgKyAxLCBzeiAtIDEpOwogICAgcmVzICs9IChsbCl4c1tyXSAqIGNudFIgLSBzdW14UjsKICAgIHJldHVybiByZXM7Cn0KCnZvaWQgc29sdmUoaW50IGwsaW50IHIsaW50IGZyb20saW50IHRvKXsKICAgIGlmKGwgPiByKQogICAgICAgIHJldHVybjsKICAgIGludCBtID0gKGwgKyByKSA+PiAxOwogICAgaW50IHN0ID0gbWF4KG0sIGZyb20pOwogICAgbGwgYmVzdCA9IGxvbmdpbmY7CiAgICBpbnQgb3B0ID0gMDsKICAgIGZvcihpbnQgaSA9IHN0OyBpIDw9IHRvOyBpKyspewogICAgICAgIGZpeChtLCBpKTsKICAgICAgICBhc3NlcnQoTCA9PSBtKTsKICAgICAgICBhc3NlcnQoUiA9PSBpKTsKICAgICAgICBjTCA9IGNSID0gMDsKICAgICAgICBsbCB0ID0gY2FsYyhtLCBpKTsKICAgICAgICBpZih0IDwgYmVzdCl7CiAgICAgICAgICAgIGJlc3QgPSB0OwogICAgICAgICAgICBvcHQgPSBpOwogICAgICAgIH0KICAgIH0KICAgIGlmKGJlc3QgPCBhbnMpewogICAgICAgIGFucyA9IGJlc3Q7CiAgICB9CiAgICBzb2x2ZShtICsgMSwgciwgb3B0LCB0byk7CiAgICBzb2x2ZShsLCBtIC0gMSwgZnJvbSwgb3B0KTsKfQoKbGwgc29sdmVfdHdvKCl7CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKyl7CiAgICAgICAgaWYocDFbaV0gPT0gcDJbaV0pCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIHZiZWdzW2dldGlkKHgyW2ldKV0ucHVzaF9iYWNrKGlpKHgxW2ldLCBpKSk7CiAgICAgICAgdmVuZHNbZ2V0aWQoeDFbaV0pXS5wdXNoX2JhY2soaWkoeDJbaV0sIGkpKTsKICAgIH0KICAgIGludCBzeiA9IHhzLnNpemUoKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgaSsrKXsKICAgICAgICBzb3J0KGFsbCh2YmVnc1tpXSkpOwogICAgICAgIHJldmVyc2UoYWxsKHZiZWdzW2ldKSk7CiAgICAgICAgc29ydChhbGwodmVuZHNbaV0pKTsKICAgIH0KICAgIG1lbXNldCh1c2VkLCAtMSwgc2l6ZW9mIHVzZWQpOwogICAgaW5pdCgpOwogICAgc29sdmUoMCwgc3ogLSAxLCAwLCBzeiAtIDEpOwogICAgcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKXsKCiNpZmRlZiBLQVpBUgogICAgZnJlb3BlbigiZi5pbnB1dCIsInIiLHN0ZGluKTsKICAgIGZyZW9wZW4oImYub3V0cHV0IiwidyIsc3Rkb3V0KTsKICAgIGZyZW9wZW4oImVycm9yIiwidyIsc3RkZXJyKTsKI2VuZGlmCgogICAgaW50IGsgPSByZWFkKCk7CiAgICBuID0gcmVhZCgpOwoKICAgIGxsIG1vcmUgPSAwOwogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspewogICAgICAgIHNjYW5mKCIgJWMgJWQgJWMgJWQiLCBwMSArIGksIHgxICsgaSwgcDIgKyBpLCB4MiArIGkpOwogICAgICAgIGlmKHgxW2ldID4geDJbaV0pCiAgICAgICAgICAgIHN3YXAoeDFbaV0sIHgyW2ldKTsKICAgICAgICB4cy5wdXNoX2JhY2soeDFbaV0pOwogICAgICAgIHhzLnB1c2hfYmFjayh4MltpXSk7CiAgICAgICAgeHMucHVzaF9iYWNrKHgxW2ldICsgeDJbaV0pOwogICAgICAgIG1vcmUgKz0geDJbaV0gLSB4MVtpXTsKICAgICAgICBpZihwMVtpXSAhPSBwMltpXSkKICAgICAgICAgICAgKyttb3JlOwogICAgfQoKICAgIHNvcnQoYWxsKHhzKSk7CiAgICB4cy5lcmFzZSh1bmlxdWUoYWxsKHhzKSksIHhzLmVuZCgpKTsKCiAgICBwcmUoKTsKCiAgICBpZihrID09IDEpewogICAgICAgIHByaW50ZigiJWxsZFxuIiwgc29sdmVfb25lKCkgKiAyICsgbW9yZSk7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CgogICAgcHJpbnRmKCIlbGxkXG4iLCBzb2x2ZV90d28oKSAqIDIgKyBtb3JlKTsKCiAgICByZXR1cm4gMDsKfQ==