#include <bits/stdc++.h>
const int INF = (int)1e9 + 7;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
template <class X, class Y>
X& remax(X& x, Y y) {
  return x = (x < y ? y : x);
}
int solve(const int n, const int m, const int k, std::vector<pii> segs) {
  assert((int)(segs).size() == n);
  vi x{0, 1, m};
  for (auto& it : segs) {
    x.insert(x.end(), {it.first - 1, it.first, it.first + 1});
    x.insert(x.end(), {it.second - 1, it.second, it.second + 1});
  }
  std::sort((x).begin(), (x).end());
  x.erase(std::unique((x).begin(), (x).end()), (x).end());
  vvi open((int)(x).size()), close((int)(x).size());
  for (int i = 0; i < (int)(segs).size(); i++) {
    segs[i].first = int(
        std::lower_bound((x).begin(), (x).end(), segs[i].first) - x.begin());
    segs[i].second = int(
        std::lower_bound((x).begin(), (x).end(), segs[i].second) - x.begin());
    open[segs[i].first].push_back(i);
    close[segs[i].second].push_back(i);
  }
  vi prevStack(k, -1), currStack(k, -1);
  auto openAll = [&](int i) {
    for (int id : open[i]) {
      for (int j = 0; j < k; j++) {
        if (currStack[j] == -1) {
          currStack[j] = id;
          break;
        }
      }
    }
  };
  auto closeAll = [&](int i) {
    for (int id : close[i]) {
      for (int j = 0; j < k; j++) {
        if (currStack[j] == id) {
          currStack[j] = -1;
          break;
        }
      }
    }
  };
  vi dp(1 << k, -INF), max(1 << k, -INF);
  dp[0] = 0;
  for (int i = 1; i < (int)(x).size(); i++) {
    openAll(i);
    int prevFilter = 0, currFilter = 0;
    for (int bit = 0; bit < k; bit++) {
      if (currStack[bit] != -1) {
        currFilter |= (1 << bit);
      }
      if (prevStack[bit] == currStack[bit] && prevStack[bit] != -1) {
        prevFilter |= (1 << bit);
      }
    }
    std::fill((max).begin(), (max).end(), -INF);
    for (int mask = 0; mask < (1 << k); mask++) {
      remax(max[mask & prevFilter], dp[mask]);
    }
    std::fill((dp).begin(), (dp).end(), -INF);
    const int cnt = x[i] - x[i - 1];
    for (int mask = 0; mask < (1 << k); mask++) {
      int currMask = mask & currFilter;
      dp[currMask] =
          __builtin_parity(currMask) * cnt + max[currMask & prevFilter];
    }
    prevStack = currStack;
    closeAll(i);
  }
  return *std::max_element((dp).begin(), (dp).end());
}
int naive(const int n, const int m, const int k, const std::vector<pii>& segs) {
  int answ = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    int curr = 0;
    for (int i = 1; i <= m; i++) {
      int cnt = 0;
      for (int j = 0; j < n; j++) {
        if ((mask >> j) & 1) {
          cnt += (segs[j].first <= i && i <= segs[j].second);
        }
      }
      curr += cnt % 2;
    }
    remax(answ, curr);
  }
  return answ;
}
template <class X, class Y>
std::ostream& operator<<(std::ostream& os, const std::pair<X, Y>& pt) {
  return os << "{" << pt.first << ", " << pt.second << "}";
}
template <class X>
std::ostream& operator<<(std::ostream& os, const std::vector<X>& v) {
  os << "{";
  for (int i = 0; i < (int)(v).size(); i++) {
    if (i > 0) os << ", ";
    os << v[i];
  }
  return os << "}";
}
void check(const std::vector<pii>& segs, const int m) {
  int fast = solve((int)(segs).size(), m, (int)(segs).size(), segs);
  int slow = naive((int)(segs).size(), m, (int)(segs).size(), segs);
  if (fast != slow) {
    std::cerr << "m = " << m << std::endl;
    std::cerr << "segs"
              << " = " << segs << std::endl;
    std::cerr << "fast"
              << " = " << fast << std::endl;
    std::cerr << "slow"
              << " = " << slow << std::endl;
    std::exit(0);
  }
}
void test() {
  std::vector<pii> segs;
  for (int m = 1; m <= 10; m++) {
    for (int a = (1); a <= (m); a++)
      for (int b = (a); b <= (m); b++) {
        segs.push_back({a, b});
        check(segs, m);
        for (int c = (1); c <= (m); c++)
          for (int d = (c); d <= (m); d++) {
            segs.push_back({c, d});
            check(segs, m);
            for (int e = (1); e <= (m); e++)
              for (int f = (e); f <= (m); f++) {
                segs.push_back({e, f});
                check(segs, m);
                for (int g = (1); g <= (m); g++)
                  for (int h = (g); h <= (m); h++) {
                    segs.push_back({g, h});
                    check(segs, m);
                    for (int i = (1); i <= (m); i++)
                      for (int j = (i); j <= (m); j++) {
                        segs.push_back({i, j});
                        check(segs, m);
                        segs.pop_back();
                      }
                    segs.pop_back();
                  }
                segs.pop_back();
              }
            segs.pop_back();
          }
        segs.pop_back();
      }
    std::cout << "m = " << m << ",OK" << std::endl;
  }
  std::exit(0);
}
int main() {
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  std::vector<pii> segs(n);
  for (auto& it : segs) {
    scanf("%d %d", &it.first, &it.second);
  }
  printf("%d", solve(n, m, k, segs));
  return 0;
}
