#include <bits/stdc++.h>
using namespace std;
const int oo = (int)1e9;
const double PI = 2 * acos(0.0);
const double eps = 1e-9;
int dcmp(double a, double b) {
  return (fabs(a - b) <= eps) ? 0 : ((a < b) ? -1 : 1);
}
int s[5009];
double x[5009];
int n, m;
int mem[5009][5009];
int calc(int idx, int prv) {
  if (idx == n + 1) return 0;
  int& ret = mem[idx][prv];
  if (ret != -1) return ret;
  ret = calc(idx + 1, prv);
  if (s[idx] >= s[prv]) ret = max(ret, calc(idx + 1, idx) + 1);
  return ret;
}
int main() {
  cin >> n >> m;
  if (cin.fail()) return 0;
  s[0] = 0;
  for (int i = 0; i < n; i++) cin >> s[i + 1] >> x[i];
  memset(mem, -1, sizeof mem);
  cout << n - calc(1, 0) << endl;
  return 0;
}
