#include <bits/stdc++.h>
using namespace std;
const int INF_MAX = 0x7FFFFFFF;
const int INF_MIN = -(1 << 30);
const double eps = 1e-10;
const double pi = acos(-1.0);
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
inline int random(int l, int r) { return rand() % (r - l + 1) + l; }
int dir_4[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int dir_8[8][2] = {{0, 1},  {-1, 1}, {-1, 0}, {-1, -1},
                   {0, -1}, {1, -1}, {1, 0},  {1, 1}};
int val[5005];
int f[5005];
int main() {
  memset(f, 0, sizeof(f));
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d%*f", val + i);
  }
  f[0] = 1;
  int ans = 1;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (val[i] >= val[j]) f[i] = max(f[i], f[j] + 1);
    }
    f[i] = max(f[i], 1);
    ans = max(f[i], ans);
  }
  cout << n - ans << endl;
  return 0;
}
