#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int K, N;
cin >> K >> N;
vector<int> A, B;
for(int i = 0; i < N; ++i) {
string P, Q; int S, T;
cin >> P >> S >> Q >> T;
if(P != Q) {
A.push_back(S);
B.push_back(T);
}
}
N = A.size();
vector<int> perm(N);
for(int i = 0; i < N; ++i) perm[i] = i;
sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] + B[i] < A[j] + B[j]; });
vector<int> SA(N), SB(N);
for(int i = 0; i < N; ++i) SA[i] = A[perm[i]], SB[i] = B[perm[i]];
A = SA, B = SB;
vector<long long> da(N + 1), db(N + 1);
long long sum = 0, all = 0, last = -1;
priority_queue<int> que;
for(int i = 1; i <= N; ++i) {
que.push(-A[i - 1]);
que.push(-B[i - 1]);
last = -que.top();
sum += last;
all += A[i - 1] + B[i - 1];
da[i] = (last * i - sum) + ((all - sum) - last * i);
}
sum = 0, all = 0, last = -1;
que = priority_queue<int>();
for(int i = 1; i <= N; ++i) {
que.push(A[N - i]);
que.push(B[N - i]);
last = que.top();
sum += last;
all += A[N - i] + B[N - i];
db[N - i] = (sum - last * i) + (last * i - (all - sum));
}
long long ans = 1LL << 62;
for(int i = 0; i < (K == 1 ? 1 : N); ++i) {
ans = min(ans, da[i] + db[i]);
}
cout << ans << endl;
return 0;
}
