#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int INF = 1000000001;
const long long LINF = 1000000000000000001LL;
struct Network {
  struct edge {
    int u, v;
    int flow, cap;
    int rev;
  };
  const int FINF = INF;
  int n, src, dest;
  vector<vector<edge>> G;
  vector<int> start, dist;
  Network(int n) : n(n), G(n), start(n), dist(n) {}
  bool bfs(int s, int t, int n) {
    for (int i = (0); i <= (n - 1); ++i) dist[i] = -1;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (edge &e : G[u])
        if (e.flow < e.cap && dist[e.v] == -1) {
          dist[e.v] = dist[u] + 1;
          q.push(e.v);
        }
    }
    return dist[t] != -1;
  }
  int dfs(int x, int t, int mini) {
    int ans = 0;
    if (x == t) return mini;
    if (mini <= 0) return 0;
    for (int &i = start[x]; i < (int)(G[x]).size(); ++i) {
      edge &e = G[x][i];
      if (dist[x] + 1 == dist[e.v] && e.flow < e.cap) {
        int added = dfs(e.v, t, min(mini, e.cap - e.flow));
        e.flow += added;
        G[e.v][e.rev].flow -= added;
        mini -= added;
        ans += added;
        if (mini <= 0) break;
      }
    }
    return ans;
  }
  int getFlow(int s, int t) {
    int ans = 0;
    while (bfs(s, t, n)) {
      for (int i = (0); i <= (n - 1); ++i) start[i] = 0;
      ans += dfs(s, t, INF);
    }
    return ans;
  }
  void addEdge(int u, int v, int cap) {
    int sizeU = (int)(G[u]).size(), sizeV = (int)(G[v]).size();
    G[u].push_back({u, v, 0, cap, sizeV});
    G[v].push_back({v, u, 0, 0, sizeU});
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> m >> n;
  const int v = 3 * n + m + 2;
  const int src = v - 2, sink = v - 1;
  const int inf = m;
  Network net(v);
  for (int i = (0); i <= (m - 1); ++i) {
    net.addEdge(src, i, 1);
  }
  for (int i = (0); i <= (n - 1); ++i) {
    if (i < n - 1) {
      net.addEdge(m + i, m + i + 1, inf);
      net.addEdge(n + m + i + 1, n + m + i, inf);
    }
    net.addEdge(m + i, 2 * n + m + i, 1);
    net.addEdge(n + m + i, 2 * n + m + i, 1);
    net.addEdge(2 * n + m + i, sink, 1);
  }
  for (int i = (0); i <= (m - 1); ++i) {
    int l, r;
    cin >> l >> r;
    net.addEdge(i, n + m + l, 1);
    net.addEdge(i, m + r, 1);
  }
  cout << m - net.getFlow(src, sink);
  return 0;
}
