#include <bits/stdc++.h>
using namespace std;
int a[5005];
int main() {
  int i, j, n, m, len = 0, tp;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d%*s", &tp);
    j = upper_bound(a, a + len, tp) - a;
    a[j] = tp;
    if (j == len) len++;
  }
  printf("%d\n", n - len);
  return 0;
}
