#include <bits/stdc++.h>
using namespace std;
int lis(vector<long long> A, int n) {
  vector<long long> tail(n);
  tail[0] = A[0];
  int len = 1;
  for (int i = 1; i < A.size(); i++) {
    if (A[i] < tail[0]) {
      tail[0] = A[i];
    }
    if (A[i] > tail[len - 1]) {
      tail[len++] = A[i];
    } else {
      *lower_bound(tail.begin(), tail.begin() + len, A[i]) = A[i];
    }
  }
  return len;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> a(n);
  float t;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> t;
    a[i] *= 10000;
    a[i] += 2;
  }
  for (int i = 0, j = 1; i < n; i++, j++) {
    a[i] += j;
  }
  cout << n - lis(a, n) << endl;
  return 0;
}
