#include <bits/stdc++.h>
using namespace std;
int lesss[5555][5555];
int mas[5555][5555];
int a[5555];
int n, m;
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    double x;
    scanf("%d %lf", &a[i], &x);
    a[i]--;
  }
  for (int j = 0; j < m; j++) {
    for (int i = n - 1; i >= 0; i--) {
      lesss[i][j] = lesss[i + 1][j] + (a[i] < j);
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      mas[i][j] = mas[i + 1][j];
      if (a[i] > j) {
        mas[i][j] =
            min(mas[i][a[i]] + lesss[i][a[i]] - lesss[i][j], mas[i + 1][j] + 1);
      }
    }
  }
  printf("%d", mas[0][0]);
  return 0;
}
