#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct range { int l, r; }; inline bool operator <(const range& a, const range& b) { return a. l + a. r < b. l + b. r; }
struct bridge { static const int maxn = 200009; int ha[maxn], hb[maxn], ta, tb; dint sa, sb; inline void clr() { ta = tb = sa = sb = 0; } bridge() { clr(); } void balance() { while (ta > tb + 1) { hb[tb] = -ha[0]; sa -= ha[0]; sb += hb[tb]; pop_heap(ha, ha + ta –); push_heap(hb, hb + ++ tb); } while (ta < tb + 1) { ha[ta] = -hb[0]; sb -= hb[0]; sa += ha[ta]; pop_heap(hb, hb + tb –); push_heap(ha, ha + ++ ta); } } inline void ins(int x) { if (x <= ha[0]) { sa += x; ha[ta] = x; push_heap(ha, ha + ++ ta); } else { sb -= x; hb[tb] = -x; push_heap(hb, hb + ++ tb); } balance(); } inline dint qry() { return _l ha[0] * (ta - tb) - sa - sb; } };
const int maxn = 100009; const dint dinf = 0x3f3f3f3f3f3f3f3fll;
int n, t, c, a[maxn « 1]; dint sa[maxn], sb[maxn]; range b[maxn]; bridge rb;
dint oneBridge() { dint ans(0); t = 0; for (int i = 0; i < n; ++ i) { char xp[3], yp[3]; int u, v; scanf("%s%d%s%d", xp, &u, yp, &v); if (xp[0] != yp[0]) { a[t ++] = u; a[t ++] = v; } else ans += abs(v - u); } sort(a, a + t); int m(a[t » 1]); for (int i = 0; i < t; ++ i) ans += abs(m - a[i]); return ans + (t » 1); }
inline dint dist(const range& a, const int& p) { return abs(a. l - p) + abs(a. r - p); }
dint twoBridge() { dint ans(0); t = 0; for (int i = 0; i < n; ++ i) { char xp[3], yp[3]; int u, v; scanf("%s%d%s%d", xp, &u, yp, &v); if (xp[0] != yp[0]) { if (u > v) swap(u, v); b[t]. l = u, b[t]. r = v; ++ t; } else ans += abs(v - u); } if (!t) return ans; sort(b, b + t); rb. clr(); for (int i = 0; i < t; ++ i) { rb. ins(b[i]. l); rb. ins(b[i]. r); sa[i] = rb. qry(); } rb. clr(); sb[t] = 0; for (int i = t - 1; i >= 0; – i) { rb. ins(b[i]. l); rb. ins(b[i]. r); sb[i] = rb. qry(); } dint sx(sb[0]); //for (int i = 0; i < t; ++ i) //fprintf(stderr, “%d %d\n”, b[i]. l, b[i]. r); // for (int i = 0; i < t; ++ i) //fprintf(stderr, “%lld %lld %lld\n”, sa[i], sb[i + 1], sa[i] + sb[i + 1]); for (int i = 0; i < t; ++ i) sx = min(sx, sa[i] + sb[i + 1]); return ans + t + sx; }
int main() { int t; scanf("%d%d", &t, &n); dint ans; if (t == 1) ans = oneBridge(); else ans = twoBridge(); printf(lld “\n”, ans); }