#include <bits/stdc++.h>
using namespace std;
using namespace std;
int n, m, a[6000];
int memo[5001][5001];
int solve(int i, int j) {
  if (i == n) return 0;
  if (memo[i][j] != -1) return memo[i][j];
  int b = (a[i] != j);
  int c1 = 0, c2 = 1e9;
  c1 = b + solve(i + 1, j);
  if (j < m) c2 = solve(i, j + 1);
  return memo[i][j] = min(c1, c2);
}
int main() {
  memset(memo, -1, sizeof(memo));
  double t;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i] >> t;
  cout << solve(0, 1) << endl;
  return 0;
}
