#include <bits/stdc++.h>
using namespace std;
int dp[5002][5002], v[5005], a[5005];
bool viz[5002][5002];
int MAX[14][5005], Log2[5005];
int MIN[14][5005], dp1[5005];
inline int QueryMAX(int X, int Y) {
  int d = Y - X + 1;
  if (X == Y) return a[X];
  int log = Log2[d];
  return max(MAX[log][X], MAX[log][Y - (1 << log) + 1]);
}
inline int QueryMIN(int X, int Y) {
  int d = Y - X + 1;
  if (X == Y) return a[X];
  int log = Log2[d];
  return min(MIN[log][X], MIN[log][Y - (1 << log) + 1]);
}
inline int DP(const int Left, const int Right) {
  if (Left == Right) return 0;
  if (viz[Left][Right]) return dp[Left][Right];
  viz[Left][Right] = 1;
  int x = 1 + DP(Left + 1, Right);
  if (a[Left] == QueryMIN(Left, Right)) --x;
  int y = 1 + DP(Left, Right - 1);
  if (a[Right] == QueryMAX(Left, Right)) --y;
  dp[Left][Right] = min(x, y);
  return dp[Left][Right];
}
int main() {
  cin.sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  double ch;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> ch;
    MAX[0][i] = MIN[0][i] = a[i];
  }
  for (int i = 2; i <= n; ++i) Log2[i] = Log2[i >> 1] + 1;
  for (int j = 1; (1 << j) <= n; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      MAX[j][i] = max(MAX[j - 1][i], MAX[j - 1][i + (1 << (j - 1))]),
      MIN[j][i] = min(MIN[j - 1][i], MIN[j - 1][i + (1 << (j - 1))]);
  int sol = DP(1, n);
  int cnt = 1;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j)
      if (a[j] == i) v[j] = cnt++;
  }
  int maxx = 0;
  for (int i = 1; i <= n; ++i) {
    dp1[i] = 1;
    for (int j = 1; j < i; ++j)
      if (v[j] < v[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
    maxx = max(dp1[i], maxx);
  }
  cout << min(n - maxx, sol) << "\n";
  return 0;
}
