#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[5010];
int dp[5010][5010];
int solve(int i, int j) {
  if (i == n) return 0;
  if (dp[i][j] >= 0) return dp[i][j];
  if (c[i] == j) {
    dp[i][j] = solve(i + 1, j);
  } else if (c[i] < j) {
    dp[i][j] = 1 + solve(i + 1, j);
  } else {
    dp[i][j] = min(1 + solve(i + 1, j), solve(i + 1, c[i]));
  }
  return dp[i][j];
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int t;
    double f;
    cin >> t >> f;
    c[i] = t;
    c[i]--;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) dp[i][j] = -1;
  cout << solve(0, 0);
  return 0;
}
