#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const int N = (int)1e6 + 7, mod = 1000000007, M = 2e9;
int n, m, a[5007], dp[5007][5007];
double t;
int slv(int i = 0, int c = 1) {
  if (i == n) return 0;
  if (c > m) return n - i;
  int& ret = dp[i][c];
  if (~ret) return ret;
  return ret = min(slv(i, c + 1), slv(i + 1, c) + (a[i] != c));
}
int main() {
  memset(dp, -1, sizeof dp);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d%f", a + i, &t);
  printf("%d", slv());
  return 0;
}
