#include <bits/stdc++.h>
using namespace std;
int a[5010];
int mic[5010][5010];
int main() {
  int n, m, t, MAX;
  double x;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d %lf", &a[i], &x);
  }
  for (int i = 1; i <= n; i++) {
    t = a[i];
    MAX = 0;
    for (int j = 1; j < t; j++) {
      mic[i][j] = mic[i - 1][j];
      MAX = max(MAX, mic[i - 1][j]);
    }
    mic[i][t] = max(mic[i - 1][t] + 1, MAX + 1);
    for (int j = t + 1; j <= m; j++) mic[i][j] = mic[i - 1][j];
  }
  MAX = 0;
  for (int i = 1; i <= m; i++) MAX = max(MAX, mic[n][i]);
  cout << n - MAX;
}
