#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, x[N], mem[N][N], cnt;
float f;
int solve(int i = 0, int p = -1) {
  if (i >= n) return 0;
  int &ret = mem[i][p + 1];
  if (~ret) return ret;
  return ret = max(solve(i + 1, p),
                   (p == -1 || x[i] >= x[p] ? solve(i + 1, i) + 1 : 0));
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  int temp;
  memset(mem, -1, sizeof mem);
  for (int i = 0; i < n; i++) {
    cin >> temp >> f;
    x[i] = temp;
  }
  cout << abs(solve() - n) << endl;
  return 0;
}
