#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 100;
int a[MAXN], dp[MAXN];
int GetLIS(int n) {
  dp[1] = a[1];
  int len = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] >= dp[len])
      dp[++len] = a[i];
    else {
      int j = int(upper_bound(dp + 1, dp + len + 1, a[i]) - dp);
      dp[j] = a[i];
    }
  }
  return len;
}
int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    double temp;
    for (int i = 1; i <= n; i++) scanf("%d %lf", &a[i], &temp);
    printf("%d\n", n - GetLIS(n));
  }
  return 0;
}
