// Superising:Sorted By S+T!
// Maybe too ad hoc for me!

#include <algorithm>
#include <map>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
typedef std::pair<uint,uint>Pair;
struct Set
{
    ullt sum;uint size;std::map<uint,uint>M;
    Set():sum(),size(){}
    voi insert(uint v){M[v]++,size++;sum+=v;}
    bol erase(uint v)
    {
        if(M.count(v))
        {
            if(!--M[v])M.erase(v);
            sum-=v,size--;return true;
        }
        return false;
    }
    uint min(){return M.begin()->first;}
    uint max(){return M.rbegin()->first;}
};
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint k,n;ullt ans=0;scanf("%u%u",&k,&n);std::vector<Pair>V;
    while(n--){static chr C1[5],C2[5];uint u,v;scanf("%s%u%s%u",C1,&u,C2,&v);if(*C1==*C2)ans+=u>v?u-v:v-u;else ans++,V.push_back({u,v});}
    if(k==1)
    {
        std::vector<uint>A;
        for(auto s:V)A.push_back(s.first),A.push_back(s.second);
        std::sort(A.begin(),A.end());
        for(uint i=0;i<A.size()/2;i++)ans+=A[A.size()/2-1]-A[i];
        for(uint i=A.size()/2;i<A.size();i++)ans+=A[i]-A[A.size()/2-1];
        printf("%llu\n",ans);
    }
    else
    {
        std::sort(V.begin(),V.end(),[](Pair a,Pair b){return a.first+a.second<b.first+b.second;});
        Set A1,A2,B1,B2;
        for(auto s:V)A1.insert(s.first),A1.insert(s.second);
        while(A1.size>A2.size)A2.insert(A1.max()),A1.erase(A1.max());
        ullt wil=A2.sum-A1.sum;
        for(auto s:V)
        {
            A1.erase(s.first)||A2.erase(s.first);A1.erase(s.second)||A2.erase(s.second);
            while(A1.size>A2.size)A2.insert(A1.max()),A1.erase(A1.max());
            while(A1.size<A2.size)A1.insert(A2.min()),A2.erase(A2.min());
            B1.insert(s.first),B1.insert(s.second),B2.insert(B1.max()),B1.erase(B1.max());
            B2.insert(B1.max()),B1.erase(B1.max()),B1.insert(B2.min()),B2.erase(B2.min());
            _min(wil,A2.sum-A1.sum+B2.sum-B1.sum);
        }
        ans+=wil;
        printf("%llu\n",ans);
    }
    return 0;
}