#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int n, m, ans = 0, i, j;
  double x;
  cin >> n >> m;
  vector<long long int> a(n + 2), dp(m + 2);
  for (i = 1; i <= n; i++) {
    cin >> a[i] >> x;
    dp[a[i]]++;
    for (j = 1; j < a[i]; j++) dp[a[i]] = max(dp[a[i]], dp[j] + 1);
    ans = max(ans, dp[a[i]]);
  }
  cout << (n - ans) << "\n";
  return 0;
}
