#include <bits/stdc++.h>
using namespace std;
int n, m;
int memo[5003][5003];
pair<double, int> A[5004];
map<int, bool> esta;
vector<int> todos;
int go(int pos, int cur) {
  if (pos >= n) return 0;
  if (cur > m) return n + 4;
  if (memo[pos][cur] != -1) return memo[pos][cur];
  int res = n + 4;
  if (A[pos].second == cur) res = min(res, go(pos + 1, cur));
  res = min(res, 1 + go(pos + 1, cur));
  res = min(res, go(pos, cur + 1));
  return memo[pos][cur] = res;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> A[i].second >> A[i].first;
  sort(A, A + n);
  memset(memo, -1, sizeof memo);
  int res = go(0, 0);
  cout << res << endl;
  return 0;
}
