#include <bits/stdc++.h>
using namespace std;
int i, j, n, m, t, uu, mas[5003], dp[5003], liel, k;
double a;
int bins(int l, int r, int y) {
  int c = r - (r - l) / 2;
  if (l < r) {
    if (dp[c] <= y) {
      return bins(c, r, y);
    } else {
      return bins(l, c - 1, y);
    }
  } else {
    if (dp[l] > y) {
      return 0;
    } else {
      return l;
    }
  }
}
int main() {
  std::cin.sync_with_stdio(false);
  cin >> n >> m;
  i = 0;
  while (i < n) {
    cin >> mas[i] >> a;
    i++;
  }
  i = 0;
  while (i < 5003) {
    dp[i] = 1000000007;
    i++;
  }
  dp[1] = mas[0];
  liel = 1;
  i = 1;
  while (i < n) {
    k = bins(1, liel, mas[i]) + 1;
    dp[k] = mas[i];
    liel = max(liel, k);
    i++;
  }
  i = 1;
  while (i <= n && dp[i] < 1000000007) {
    i++;
  }
  cout << n - (i - 1) << "\n";
  return 0;
}
