#include <bits/stdc++.h>
using namespace std;
const int kN = 5000 + 1;
const int kInf = 1000 * 1000 * 1000;
int dp[kN], inp[kN];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    double val;
    cin >> inp[i] >> val;
  }
  dp[0] = 1;
  for (int i = 1; i < n; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j)
      if (inp[j] <= inp[i]) dp[i] = max(dp[i], dp[j] + 1);
  }
  cout << n - *max_element(dp, dp + n);
  return 0;
}
