#include <bits/stdc++.h>
using namespace std;
int n, m, s[5010], f[5010][5010], res;
int main() {
  cin >> n >> m;
  for (int i = (int)1; i <= (int)n; ++i) {
    char foo[30];
    cin >> s[i] >> foo;
  }
  memset(f, -1, sizeof(f));
  f[1][1] = 0;
  for (int i = (int)1; i <= (int)n; ++i)
    for (int j = (int)1; j <= (int)m; ++j)
      f[i][j + 1] = max(f[i][j + 1], f[i][j]),
               f[i + 1][j] = max(f[i + 1][j], f[i][j] + (s[i] == j));
  for (int j = (int)1; j <= (int)m; ++j)
    if (f[n + 1][j] > res) res = f[n + 1][j];
  cout << n - res;
}
