#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 5e3 + 10;
const int maxm = 5e5 + 10;
const long long INF = 1e18;
long long powmod(long long x, long long y) {
  long long t;
  for (t = 1; y; y >>= 1, x = x * x % mod)
    if (y & 1) t = t * x % mod;
  return t;
}
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int n, m, pos[maxn], dp[maxn], ans = 0;
double d;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int(i) = (1); (i) < (n + 1); (i)++) {
    int x, tmp = 0;
    cin >> x >> d;
    for (int(j) = (0); (j) < (x + 1); (j)++) tmp = max(dp[j], tmp);
    dp[x] = max(dp[x], tmp + 1);
    ans = max(ans, dp[x]);
  }
  cout << n - ans << "\n";
  return 0;
}
