#include <bits/stdc++.h>
using namespace std;
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vector) {
  for (size_t i = 0; i < vector.size(); ++i) {
    os << vector[i] << " ";
  }
  os << "\n";
  return os;
}
vector<int> Input(int* m) {
  int size;
  cin >> size >> *m;
  vector<int> v(size);
  for (int i = 0; i < size; ++i) {
    double x;
    cin >> v[i] >> x;
  }
  return v;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int m;
  vector<int> v = Input(&m);
  vector<int> d(v.size(), 1);
  for (int i = 1; i < v.size(); ++i) {
    for (int j = 0; j < i; ++j) {
      if (v[j] <= v[i]) {
        d[i] = max(d[i], d[j] + 1);
      }
    }
  }
  cout << (v.size() - *max_element(d.begin(), d.end())) << "\n";
  return 0;
}
