#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
template <typename T>
void readv(vector<T>& v, int n) {
  for (int i = 0; i < n; ++i) {
    T tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
}
int lcs[5005][5005];
int main(int argc, char** argv) {
  int n, m;
  cin >> n >> m;
  vector<int> species;
  for (int i = 0; i < n; ++i) {
    int tmp;
    float xxx;
    cin >> tmp >> xxx;
    species.push_back(tmp);
  }
  vector<int> sorted_species(species);
  sort(sorted_species.begin(), sorted_species.end());
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
      if (sorted_species[i - 1] == species[j - 1]) {
        lcs[i][j] = max(lcs[i][j], lcs[i - 1][j - 1] + 1);
      }
    }
  }
  cout << n - lcs[n][n] << endl;
  return 0;
}
