Butler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not.

The butler wants to show Arkady n gardens. Each garden is a row of m cells, the i-th garden has one fountain in each of the cells between li and ri inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady.

Ostin wants to choose two integers a ≤ b and show only part of each of the gardens that starts at cell a and ends at cell b. Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from a to b.

Help Ostin to find the total length of all such segments, i.e. sum up the value (b - a + 1) for each suitable pair (a, b).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of gardens and the length of each garden.

n lines follow. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ m) — the bounds of the segment that contains fountains in the i-th garden.

Output

Print one integer: the total length of all suitable segments.

Examples

Input

1 5
2 4


Output

23


Input

3 6
2 4
3 6
4 4


Output

19

Note

In the first example the following pairs suit Ostin: (a, b): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).

In the second example the following pairs suit Ostin: (a, b): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6).
#include <bits/stdc++.h>
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline bool repr(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool repl(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
struct Cg {
  inline char operator()() { return getchar(); }
};
struct Cp {
  inline void operator()(char x) { putchar(x); }
};
inline bool IS(char x) { return x == 10 || x == 13 || x == ' '; }
template <typename T>
struct Fr {
  T P;
  inline Fr &operator,(int &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  inline operator int() {
    int x;
    *this, x;
    return x;
  }
  inline Fr &operator,(long long &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P())
      ;
    return *this;
  }
  inline operator char() {
    char x;
    *this, x;
    return x;
  }
  inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P())
      ;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  inline Fr &operator,(double &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  inline operator double() {
    double x;
    *this, x;
    return x;
  }
  inline Fr &operator,(long double &x) {
    x = 0;
    char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  inline Fr &operator,(unsigned int &x) {
    x = 0;
    char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  inline Fr &operator,(unsigned long long &x) {
    x = 0;
    char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
Fr<Cg> in;
template <typename T>
struct Fw {
  T P;
  inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(unsigned int x) {
    if (x) {
      char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(unsigned int x) {
    if (x) {
      char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(unsigned long long x) {
    if (x) {
      char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator()(unsigned long long x) {
    if (x) {
      char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
Fw<Cp> out;
const int N = 200007, M = 100007;
struct node {
  int ma, mac, tag;
  long long mas;
} f[1 << 18];
inline void st(int x, int y) { f[x].ma += y, f[x].tag += y; }
inline void pd(int x) {
  if (f[x].tag) {
    st(x << 1, f[x].tag);
    st(x << 1 | 1, f[x].tag);
    f[x].tag = 0;
  }
}
inline void copy(node &a, node &b) {
  a.ma = b.ma, a.mac = b.mac, a.mas = b.mas;
}
inline void pu(int x) {
  if (f[x << 1].ma < f[x << 1 | 1].ma)
    copy(f[x], f[x << 1 | 1]);
  else if (f[x << 1].ma > f[x << 1 | 1].ma)
    copy(f[x], f[x << 1]);
  else {
    f[x].ma = f[x << 1].ma;
    f[x].mac = f[x << 1].mac + f[x << 1 | 1].mac;
    f[x].mas = f[x << 1].mas + f[x << 1 | 1].mas;
  }
}
inline void modify(int x, int l, int r, int ql, int qr, int v) {
  if (l >= ql && r <= qr) {
    st(x, v);
    return;
  }
  int t = (l + r) >> 1;
  pd(x);
  if (ql <= t) modify(x << 1, l, t, ql, qr, v);
  if (qr > t) modify(x << 1 | 1, t + 1, r, ql, qr, v);
  pu(x);
}
inline void build(int x, int l, int r) {
  f[x].ma = 0;
  f[x].tag = 0;
  if (l == r)
    f[x].mac = 1, f[x].mas = l;
  else {
    int t = (l + r) >> 1;
    build(x << 1, l, t);
    build(x << 1 | 1, t + 1, r);
    pu(x);
  }
}
int n, m, u, l[N], r[N], t[N];
inline void mod(int a, int b, int c) {
  if (a <= b) modify(1, 0, u, a, b, c);
}
struct qry {
  int l, r, v;
  qry() {}
  qry(int a, int b, int c) { l = a, r = b, v = c; }
};
std::vector<qry> q[M];
inline void add(int a, int b, qry x) {
  q[a].push_back(x);
  x.v = -x.v;
  q[b].push_back(x);
}
int main() {
  in, n, m;
  for (int i = 0, iend = n; i < iend; i++) {
    in, l[i], r[i];
    l[i]--, r[i]--;
  }
  u = m / 2;
  long long ans = 0;
  build(1, 0, u);
  for (int i = 0, iend = u; i <= iend; i++) q[i].clear();
  for (int i = 0, iend = n; i < iend; i++) {
    if (!(l[i] & 1) && !(r[i] & 1)) {
      mod(0, (m - 1) / 2, 1);
    } else if (!(l[i] & 1) && (r[i] & 1)) {
      mod(0, r[i] / 2, 1);
      q[r[i] / 2 + 1].push_back(qry(r[i] / 2 + 1, (m - 1) / 2, 1));
      q[r[i] / 2 + 1].push_back(qry(0, r[i] / 2, -1));
    } else if ((l[i] & 1) && !(r[i] & 1)) {
      mod(0, l[i] / 2, 1), q[l[i] / 2 + 1].push_back(qry(0, l[i] / 2, -1));
      q[l[i] / 2 + 1].push_back(qry(l[i] / 2 + 1, (m - 1) / 2, 1));
    } else if ((l[i] & 1) && (r[i] & 1)) {
      mod(0, l[i] / 2, 1);
      mod(r[i] / 2 + 1, (m - 1) / 2, 1);
      add(l[i] / 2 + 1, r[i] / 2 + 1, qry(r[i] / 2 + 1, (m - 1) / 2, -1));
      add(l[i] / 2 + 1, r[i] / 2 + 1, qry(l[i] / 2 + 1, r[i] / 2, 1));
    }
  }
  for (int i = 0, iend = u; i <= iend; i++) {
    if (i) mod(i - 1, i - 1, -1e9);
    for (__typeof(q[i].end()) j = q[i].begin(); j != q[i].end(); ++j)
      mod(j->l, j->r, j->v);
    if (f[1].ma != n) continue;
    ans += f[1].mas * 2 + (1ll - i * 2) * f[1].mac;
  }
  build(1, 0, u);
  for (int i = 0, iend = u; i <= iend; i++) q[i].clear();
  for (int i = 0, iend = n; i < iend; i++) {
    if (!(l[i] & 1) && !(r[i] & 1)) {
      mod(0, l[i] / 2 - 1, 1);
      mod(r[i] / 2, m / 2 - 1, 1);
    } else if (!(l[i] & 1) && (r[i] & 1)) {
      mod(0, l[i] / 2 - 1, 1);
      q[r[i] / 2 + 1].push_back(qry(r[i] / 2 + 1, m / 2 - 1, 1));
    } else if ((l[i] & 1) && !(r[i] & 1)) {
      mod(0, r[i] / 2 - 1, 1);
      q[l[i] / 2 + 1].push_back(qry(0, r[i] / 2 - 1, -1));
      q[l[i] / 2 + 1].push_back(qry(r[i] / 2, m / 2 - 1, 1));
    } else if ((l[i] & 1) && (r[i] & 1)) {
      mod(0, m / 2 - 1, 1);
      add(l[i] / 2 + 1, r[i] / 2 + 1, qry(0, m / 2 - 1, -1));
    }
  }
  for (int i = 0, iend = u; i <= iend; i++) {
    if (i) mod(i - 1, i - 1, -1e9);
    for (__typeof(q[i].end()) j = q[i].begin(); j != q[i].end(); ++j)
      mod(j->l, j->r, j->v);
    if (f[1].ma != n) continue;
    ans += f[1].mas * 2 + (2ll - i * 2) * f[1].mac;
  }
  build(1, 0, u);
  for (int i = 0, iend = u; i <= iend; i++) q[i].clear();
  for (int i = 0, iend = n; i < iend; i++) {
    if (!(l[i] & 1) && !(r[i] & 1)) {
      mod(0, (m - 1) / 2, 1);
      add(l[i] / 2, r[i] / 2, qry(l[i] / 2, (m - 1) / 2, -1));
    } else if (!(l[i] & 1) && (r[i] & 1)) {
      mod(0, r[i] / 2, 1);
      q[l[i] / 2].push_back(qry(0, r[i] / 2, -1));
      q[l[i] / 2].push_back(qry(r[i] / 2 + 1, (m - 1) / 2, 1));
    } else if ((l[i] & 1) && !(r[i] & 1)) {
      mod(0, l[i] / 2, 1);
      q[r[i] / 2].push_back(qry(r[i] / 2, (m - 1) / 2, 1));
    } else if ((l[i] & 1) && (r[i] & 1)) {
      mod(0, l[i] / 2, 1);
      mod(r[i] / 2 + 1, (m - 1) / 2, 1);
    }
  }
  for (int i = 0, iend = u; i <= iend; i++) {
    mod(i, i, -1e9);
    for (__typeof(q[i].end()) j = q[i].begin(); j != q[i].end(); ++j)
      mod(j->l, j->r, j->v);
    if (f[1].ma != n) continue;
    ans += f[1].mas * 2 + (-i * 2ll) * f[1].mac;
  }
  build(1, 0, u);
  for (int i = 0, iend = u; i <= iend; i++) q[i].clear();
  for (int i = 0, iend = n; i < iend; i++) {
    if (!(l[i] & 1) && !(r[i] & 1)) {
      mod(0, l[i] / 2 - 1, 1);
      mod(r[i] / 2, m / 2 - 1, 1);
      add(l[i] / 2, r[i] / 2, qry(r[i] / 2, m / 2 - 1, -1));
      add(l[i] / 2, r[i] / 2, qry(l[i] / 2, r[i] / 2 - 1, 1));
    } else if (!(l[i] & 1) && (r[i] & 1)) {
      mod(0, l[i] / 2 - 1, 1);
      q[l[i] / 2].push_back(qry(l[i] / 2, m / 2 - 1, 1));
    } else if ((l[i] & 1) && !(r[i] & 1)) {
      mod(0, r[i] / 2 - 1, 1);
      q[r[i] / 2].push_back(qry(r[i] / 2, m / 2 - 1, 1));
    } else if ((l[i] & 1) && (r[i] & 1)) {
      mod(0, m / 2 - 1, 1);
    }
  }
  for (int i = 0, iend = u; i <= iend; i++) {
    if (i) mod(i - 1, i - 1, -1e9);
    for (__typeof(q[i].end()) j = q[i].begin(); j != q[i].end(); ++j)
      mod(j->l, j->r, j->v);
    if (f[1].ma != n) continue;
    ans += f[1].mas * 2 + (1ll - i * 2) * f[1].mac;
  }
  for (int i = 0, iend = n; i < iend; i++) {
    t[l[i]]++;
    t[r[i] + 1]--;
  }
  int x = 0, y = 0;
  for (int i = 0, iend = m; i <= iend; i++) {
    x += t[i];
    if (!x && i < m)
      y++;
    else {
      for (int j = 1, jend = y; j <= jend; j++)
        ans -= (long long)j * (y - j + 1);
      y = 0;
    }
  }
  out, ans;
}
