#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define ll long long
struct A {
ll sum, s, t;
bool operator< (A& other) {
return sum < other.sum;
}
};
vector<A> arr;
multiset<int> lo1, hi1, lo2, hi2;
void Ins(multiset<int>& lo, multiset<int>& hi, ll& losum, ll& hisum, int val, int sz)
{
if(!lo.empty() && *lo.rbegin() < val)
{
hisum += val;
hi.insert(val);
}
else
{
losum += val;
lo.insert(val);
}
int mid = sz/2 + (sz%2 > 0);
if(!hi.empty() && hi.size() > sz/2)
{
losum += *hi.begin();
hisum -= *hi.begin();
lo.insert(*hi.begin());
hi.erase(hi.begin());
}
else if(!lo.empty() && lo.size() > mid)
{
losum -= *lo.rbegin();
hisum += *lo.rbegin();
hi.insert(*lo.rbegin());
lo.erase(prev(lo.end()));
}
}
void Del(multiset<int>& lo, multiset<int>& hi, ll& losum, ll& hisum, int val, int sz)
{
if(lo.find(val) != lo.end())
{
losum -= val;
lo.erase(lo.find(val));
}
else
{
hisum -= val;
hi.erase(hi.find(val));
}
int mid = sz/2 + (sz%2 > 0);
if(!hi.empty() && hi.size() > sz/2)
{
losum += *hi.begin();
hisum -= *hi.begin();
lo.insert(*hi.begin());
hi.erase(hi.begin());
}
else if(!lo.empty() && lo.size() > mid)
{
losum -= *lo.rbegin();
hisum += *lo.rbegin();
hi.insert(*lo.rbegin());
lo.erase(prev(lo.end()));
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int k, n;
cin >> k >> n;
ll ans = 0;
ll losum1 = 0, hisum1 = 0, losum2 = 0, hisum2 = 0;
for(int i = 0; i < n; i++)
{
char p, q; int s, t;
cin >> p >> s >> q >> t;
if(p == q)
ans += abs(s-t);
else
{
arr.push_back({s+t, s, t});
Ins(lo2, hi2, losum2, hisum2, s, arr.size()*2);
Ins(lo2, hi2, losum2, hisum2, t, arr.size()*2);
}
}
if(arr.empty())
{
cout << ans << '\n';
return 0;
}
if(arr.size() == 1 || k == 1)
{
ll mid = *lo2.rbegin();
cout << ans + (mid*lo2.size() - losum2) + (hisum2 - mid*hi2.size()) + arr.size() << '\n';
return 0;
}
sort(arr.begin(), arr.end());
ll val = 1e18;
for(int i = 0; i < (int)arr.size()-1; i++)
{
Ins(lo1, hi1, losum1, hisum1, arr[i].s, (i+1)*2);
Ins(lo1, hi1, losum1, hisum1, arr[i].t, (i+1)*2);
Del(lo2, hi2, losum2, hisum2, arr[i].s, arr.size()*2 - (i+1)*2);
Del(lo2, hi2, losum2, hisum2, arr[i].t, arr.size()*2 - (i+1)*2);
ll mid = *lo1.rbegin();
ll elem1 = (mid*lo1.size() - losum1) + (hisum1 - mid*hi1.size());
mid = *lo2.rbegin();
ll elem2 = (mid*lo2.size() - losum2) + (hisum2 - mid*hi2.size());
val = min(val, elem1 + elem2);
}
cout << ans + val + arr.size() << '\n';
}
