#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int last[MAXN], t[MAXN];
int ans = MAXN;
int n, m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  scanf("%d%d", &n, &m);
  for (auto i = 0; i != n; i++) {
    int _t;
    double db;
    scanf("%d%f", &_t, &db);
    t[i] = _t;
  }
  memset(last, 0, sizeof(last));
  for (auto i = 0; i != n; i++) {
    int curr = 0;
    for (auto j = 1; j != t[i] + 1; j++) curr = max(curr, last[j] + 1);
    ans = min(ans, n - curr);
    last[t[i]] = max(last[t[i]], curr);
  }
  printf("%d", ans);
  return 0;
}
