#include <bits/stdc++.h>
using namespace std;
int dp[2][5005];
int main() {
  std::ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> s(n);
  for (auto &d : (s)) {
    double first;
    cin >> d >> first;
    d--;
  }
  int now = 0, pre = 1;
  for (int i = 0; i < int(n); i++) {
    swap(now, pre);
    for (int j = 0; j < int(m); j++) {
      dp[now][j] = dp[pre][j] + int(s[i] != j);
      if (j > 0) {
        dp[now][j] = min(dp[now][j], dp[now][j - 1]);
      }
    }
  }
  cout << *min_element(dp[now], dp[now] + m);
  return 0;
}
