#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
int n, m, s[5555], lnds[5555];
double crap;
int solve() {
  memset(lnds, 0, sizeof(lnds));
  int res = 0;
  for (int i = (1); i < (n + 1); i++) {
    for (int j = (0); j < (i); j++)
      if (s[j] <= s[i]) lnds[i] = max(lnds[i], lnds[j] + 1);
    res = max(res, lnds[i]);
  }
  return n - res;
}
int main() {
  while (cin >> n >> m) {
    for (int i = (1); i < (n + 1); i++) cin >> s[i] >> crap;
    cout << solve() << endl;
  }
}
