#include <bits/stdc++.h>
using namespace std;
int const maxN = 5000 + 20;
int n, m, s[maxN], dp[maxN], mx;
double x;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = (0); i < (n); i++) {
    cin >> s[i] >> x;
  }
  for (int i = (0); i < (n); i++) {
    int res = 1;
    for (int j = (0); j < (i); j++)
      if (s[j] <= s[i] && dp[j] + 1 > res) res = dp[j] + 1;
    dp[i] = res;
  }
  for (int i = (0); i < (n); i++) mx = max(mx, dp[i]);
  return cout << n - mx, 0;
}
