#include <bits/stdc++.h>
using namespace std;
int n, m, vid, ans = 0;
double kord;
vector<int> s;
double ans_massive[10000];
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> vid >> kord;
    s.push_back(vid);
  }
  for (int i = 0; i < s.size(); ++i)
    for (int j = 0; j < i; ++j)
      if (s[i] >= s[j] && ans_massive[i] <= ans_massive[j])
        ans_massive[i] = ans_massive[j] + 1;
  ans = 0;
  for (int i = 0; i < n; ++i)
    if (ans_massive[i] > ans) ans = ans_massive[i];
  cout << n - ans - 1;
  return 0;
}
