#include <bits/stdc++.h>
using namespace std;
int findLengthOfLNDS(vector<pair<int, float> > &plants_data) {
  if (plants_data.size() == 0) return 0;
  vector<int> m;
  m.push_back(0);
  for (int i = 1; i < plants_data.size(); i++) {
    if (plants_data[m.back()].first <= plants_data[i].first) {
      m.push_back(i);
    } else {
      int b = 0, e = m.size() - 1, mid = 0, replace_at = 0;
      while (b <= e) {
        mid = (b + e) / 2;
        if (plants_data[i].first >= plants_data[m[mid]].first) {
          b = mid + 1;
        } else {
          e = mid - 1;
        }
      }
      if (plants_data[m[mid]].first <= plants_data[i].first) {
        replace_at = mid + 1;
      } else {
        replace_at = mid;
      }
      m[replace_at] = i;
    }
  }
  return m.size();
}
int main() {
  int no_plants, no_species;
  vector<pair<int, float> > plants_data;
  cin >> no_plants >> no_species;
  for (int i = 0; i < no_plants; i++) {
    int speci;
    float location;
    cin >> speci >> location;
    plants_data.push_back(make_pair(speci, location));
  }
  cout << no_plants - findLengthOfLNDS(plants_data);
  return 0;
}
