#include <bits/stdc++.h>
using namespace std;
int n, m, s[5010], res;
vector<int> d[2];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (int)1; i <= (int)n; ++i) {
    char foo[30];
    scanf("%d%s", &s[i], foo);
  }
  d[1].assign(n + 1, -1);
  d[1][1] = 0;
  for (int i = (int)1; i <= (int)n; ++i) {
    d[0] = d[1];
    d[1].assign(n + 1, -1);
    for (int j = (int)1; j <= (int)m; ++j)
      d[0][j + 1] = max(d[0][j + 1], d[0][j]), d[1][j] = d[0][j] + (s[i] == j);
  }
  for (int j = (int)1; j <= (int)m; ++j) res = max(res, d[1][j]);
  cout << n - res;
}
