#include <bits/stdc++.h>
using namespace std;
int n, m, a[5009], dp[5009][5009];
double x;
long long best(long long d, long long i) {
  if (d > n) return 0;
  if (dp[d][i] != -1) return dp[d][i];
  if (a[i] <= a[d]) return dp[d][i] = max(best(d + 1, d) + 1, best(d + 1, i));
  return dp[d][i] = best(d + 1, i);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  a[0] = -1;
  memset(dp, -1, sizeof dp);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i] >> x;
  cout << n - best(1, 0) << endl;
  return 0;
}
