#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 321;
int arr[maxn], LIS_arr[maxn];
int n;
int LIS() {
  int ja = 1;
  LIS_arr[0] = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] >= LIS_arr[ja - 1])
      LIS_arr[ja++] = arr[i];
    else
      *upper_bound(LIS_arr, LIS_arr + ja, arr[i]) = arr[i];
  }
  return ja;
}
int main() {
  double d;
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> arr[i] >> d;
  cout << n - LIS() << endl;
  return 0;
}
