#include <bits/stdc++.h>
using namespace std;
int dp[5010], type[5010];
int main() {
  int n, m;
  double y;
  while (cin >> n >> m) {
    for (int i = (int)0; i < (int)n; i++) cin >> type[i] >> y;
    memset(dp, 0, sizeof(dp));
    for (int i = (int)0; i < (int)n; i++) {
      for (int j = type[i]; j > 0; --j)
        dp[type[i]] = max(dp[type[i]], 1 + dp[j]);
    }
    int res = 0;
    for (int type = (int)1; type < (int)m + 1; type++) res = max(res, dp[type]);
    cout << n - res << endl;
  }
  return 0;
}
