#include <bits/stdc++.h>
using namespace std;
int n, m, a;
int man[5005];
int vec[5005];
int dp[5005];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a);
    float f;
    scanf("%f", &f);
    if (i == 0) {
      dp[i] = 0;
      for (int j = 1; j <= m; j++) {
        if (a <= j) {
          man[j] = 0;
          vec[j] = 0;
        } else {
          man[j] = 0;
          vec[j] = 1;
        }
      }
    } else {
      dp[i] = min(dp[i - 1] + 1, man[a] + vec[a]);
      for (int j = 1; j <= m; j++)
        if (a > j) vec[j]++;
      int x = man[a];
      for (int j = a; j <= m; j++)
        man[j] = min(man[j] + 1, x + vec[a] - vec[j]);
    }
  }
  printf("%d", dp[n - 1]);
  return 0;
}
