#include <bits/stdc++.h>
using namespace std;
const int MAX = 5000;
int a[MAX];
int len[MAX];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = (0); i < (n); ++i) {
    double f;
    scanf("%d %lf", &a[i], &f);
    len[i] = 1;
  }
  int best_len = 1;
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (i); ++j) {
      if (a[j] <= a[i]) len[i] = max(len[i], 1 + len[j]);
      best_len = max(best_len, len[i]);
    }
  }
  printf("%d\n", n - best_len);
  return 0;
}
