#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 5;
int n, m, type[maxn], dp[maxn];
double x;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = (1); i <= (n); i++) cin >> type[i] >> x;
  for (int i = (1); i <= (n); i++) {
    int j = type[i];
    for (int k = j; k >= 1; k--) dp[j] = max(dp[j], 1 + dp[k]);
    cout << "\n";
  }
  int ans = 0;
  for (int i = (1); i <= (n); i++) ans = max(ans, dp[i]);
  cout << n - ans;
  return 0;
}
