#include <bits/stdc++.h>
using namespace std;
template <class _T>
inline string tostr(const _T& a) {
  ostringstream os("");
  os << a;
  return os.str();
}
const double pi = 3.1415926;
const long double eps = 1e-9;
const int N = (int)1e5 + 5;
const int INF = (int)1e9 + 10;
int main() {
  int n, m;
  cin >> n >> m;
  int k;
  double x;
  int* types = new int[n];
  for (int i = 0; i < n; i++) {
    cin >> k >> x;
    types[i] = k;
  }
  int** d = new int*[n];
  d[0] = new int[m + 1];
  for (int i = 0; i <= m; i++) d[0][i] = 0;
  d[0][types[0]] = 1;
  for (int i = 1; i < n; i++) {
    d[i] = new int[m + 1];
    for (int j = 1; j <= m; j++) {
      if (types[i] == j) {
        int mx = -INF;
        for (int z = 1; z <= j; z++) mx = max(mx, d[i - 1][z]);
        d[i][j] = mx + 1;
      } else
        d[i][j] = d[i - 1][j];
    }
  }
  int mx = -INF;
  for (int i = 1; i <= m; i++) mx = max(mx, d[n - 1][i]);
  cout << n - mx;
}
