#include <stdio.h>
#include <string.h>
#define N 200000
#define M 200000
#define N1 (N * 2 + M)
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(M))) */
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N1], yy[N1], tt[N];
int compare_x(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : i - j; }
int compare_t(int i, int j) { return tt[j] - tt[i]; }
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int st[N_ * 2], n_;
void build(int *aa, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
memset(st, -1, n_ * 2 * sizeof *st);
for (i = 0; i < n; i++)
st[n_ + aa[i]] = max(st[n_ + aa[i]], i);
for (i = n_ - 1; i > 0; i--)
st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}
int st_query(int l, int r) {
int x = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
x = max(x, st[l++]);
if ((r & 1) == 0)
x = max(x, st[r--]);
}
return x;
}
int ft[M];
void ft_update(int i, int n, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int ft_query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int main() {
static int ii[N1];
int n, n1, m, i, i_, j, l, r, x, y, tmp, flip;
long long sum;
scanf("%d%d", &n, &m), n1 = n * 2 + m;
for (i = 0; i < n1; i++)
scanf("%d", &xx[i]);
for (i = 0; i < n1; i++)
ii[i] = i;
compare = compare_x, sort(ii, 0, n1);
for (i = 0, x = 0, y = -1; i < n1; i++) {
i_ = ii[i];
if (i_ >= n * 2 && x != xx[i_])
x = xx[i_], y++;
yy[i_] = y;
}
build(yy + n * 2, m);
for (i = 0; i < n; i++) {
l = yy[i << 1 | 0], r = yy[i << 1 | 1];
if (l > r)
tmp = l, l = r, r = tmp;
tt[i] = st_query(l + 1, r);
}
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_t, sort(ii, 0, n);
sum = 0;
for (i = 0, j = m - 1; i < n; i++) {
i_ = ii[i];
while (j > tt[i_])
ft_update(m - 1 - yy[n * 2 + j--], m, 1);
flip = 0;
if (tt[i_] != -1 && xx[i_ << 1 | 0] < xx[i_ << 1 | 1])
flip ^= 1;
if (ft_query(m - 2 - yy[i_ << 1 | 0]) % 2 != 0)
flip ^= 1;
sum += xx[i_ << 1 | flip];
}
printf("%lld\n", sum);
return 0;
}
