#include <bits/stdc++.h>
using namespace std;
constexpr auto EPS = 1e-9;
clock_t T;
void GOAT() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}
int mem[5009][5009], s[5009], n, m;
double p[5007];
int solve(int idx, int pre) {
  if (idx == n) return 0;
  int& ret = mem[idx][pre];
  if (~ret) return ret;
  ret = solve(idx + 1, pre);
  if (s[idx] >= s[pre]) ret = max(ret, solve(idx + 1, idx) + 1);
  return ret;
}
int main() {
  GOAT();
  memset(mem, -1, sizeof mem);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i] >> p[i];
  cout << n - solve(0, n) << "\n";
}
