rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
//---------- FHQ treap ----------//
mt19937 rng(time(0));
int root,tot;
struct node{int sum,val,pri,ls,rs,sz;}tr[N];
void clear()
{
    tot=root=0;
    memset(tr,0,sizeof tr);
}
int New(int x)
{
    ++tot;
    tr[tot].sum=tr[tot].val=x;
    tr[tot].pri=rng();
    tr[tot].sz=1;
    return tot;
}
void pushup(int p)
{
    tr[p].sz=tr[tr[p].ls].sz+tr[tr[p].rs].sz+1;
    tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum+tr[p].val;
}
void split(int p,int x,int &L,int &R)
{
    if(!p)
    {
        L=R=0;
        return ;
    }
    if(tr[p].val<=x)
    {
        L=p;
        split(tr[p].rs,x,tr[p].rs,R);
    }
    else
    {
        R=p;
        split(tr[p].ls,x,L,tr[p].ls);
    }
    pushup(p);
}
int merge(int L,int R)
{
    if(!L||!R)
        return L+R;
    if(tr[L].pri<=tr[R].pri)
    {
        tr[L].rs=merge(tr[L].rs,R);
        pushup(L);
        return L;
    }
    tr[R].ls=merge(L,tr[R].ls);
    pushup(R);
    return R;
}
void insert(int x)
{
    int L,R;
    split(root,x,L,R);
    root=merge(merge(L,New(x)),R);
}
int kth(int p,int k)
{
    while(1)
    {
        if(k==tr[tr[p].ls].sz+1)
            return tr[p].val;
        if(k<=tr[tr[p].ls].sz)
            p=tr[p].ls;
        else
        {
            k-=tr[tr[p].ls].sz+1;
            p=tr[p].rs;
        }
    }
    return 114514;
}
int query()//求大于中位数的和减去小于等于中位数的
{
    int x=kth(root,tr[root].sz>>1);
    int L,R;
    split(root,x,L,R);
    int res=tr[R].sum-tr[L].sum;
    root=merge(L,R);
    return res;
}
//---------- FHQ treap ----------//
struct Node{
    int s,t;
    bool operator<(const Node &b)const{return s+t<b.s+b.t;}
}a[N];
int f[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K,n;
    int ans1=0;//ans1:维护同侧的和
    cin>>K>>n;
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        char p,q;
        int x,y;
        cin>>p>>x>>q>>y;
        if(p==q)ans1+=abs(x-y);
        else
        {
            ++cnt;
            a[cnt].s=x;
            a[cnt].t=y;
        }
    }
    sort(a+1,a+cnt+1);
    ans1+=cnt;
    for(int i=1;i<=cnt;++i)
    {
        insert(a[i].s);
        insert(a[i].t);
        f[i]=query();
    }
    int ans=f[cnt];
    if(K==2)
    {
        clear();
        for(int i=cnt;i;--i)
        {
            insert(a[i].s);
            insert(a[i].t);
            ans=min(ans,query()+f[i-1]);
        }
    }
    cout<<ans+ans1;
}