#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long counts[5005];
vector<pair<long long, double>> a;
long long dp[5005];
void lis() {
  for (long long i = 1; i < n; i++) {
    for (long long j = 0; j < i; j++) {
      if (a[i].first >= a[j].first && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
      }
    }
  }
}
int main(int argc, const char* argv[]) {
  cin >> n >> m;
  memset(counts, 0, sizeof(counts));
  for (long long i = 0; i < n; i++) {
    long long x;
    double y;
    cin >> x >> y;
    a.push_back(make_pair(x, y));
    counts[x]++;
  }
  for (long long i = 0; i < n; i++) dp[i] = 1;
  lis();
  long long maxs = 0;
  for (long long i = 0; i < n; i++) {
    if (dp[i] > maxs) maxs = dp[i];
  }
  cout << n - maxs;
}
