#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, max = 0, lcs[5000] = {0};
  vector<int> plants(5000);
  float x;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> plants[i] >> x;
  }
  lcs[0] = 1;
  for (int next = 1; next < n; next++) {
    lcs[next] = 1;
    for (int pre = next - 1; pre >= 0; pre--) {
      if (plants[next] >= plants[pre] && lcs[pre] + 1 > lcs[next]) {
        lcs[next] = lcs[pre] + 1;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    max = lcs[i] > max ? lcs[i] : max;
  }
  cout << n - max << endl;
}
