#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
int dp[5010];
int type[5010];
int main() {
  int n, m, mx = 0;
  double x;
  scanf("%d%d", &n, &m);
  for (int(i) = (1); (i) <= (n); ++(i)) scanf("%d%lf", &type[i], &x);
  for (int(i) = (1); (i) <= (n); ++(i)) {
    dp[i] = 1;
    for (int(j) = (1); (j) <= (i - 1); ++(j))
      if (i != j && type[j] <= type[i]) dp[i] = max(dp[i], dp[j] + 1);
  }
  for (int(i) = (1); (i) <= (n); ++(i)) mx = max(mx, dp[i]);
  printf("%d\n", n - mx);
  return 0;
}
