#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int INF = 0x7f7f7f7f;
const double pi = 4.0 * atan(1.0);
int cases;
int num[MAXN], dp[MAXN];
void solve(int m) {
  for (int i = 1; i <= m; i++) {
    dp[i] = 1;
    for (int j = 1; j < i; j++) {
      if (num[j] <= num[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
  }
  printf("%d\n", m - *max_element(dp + 1, dp + m + 1));
}
int main() {
  int n, m;
  double t;
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= m; i++) {
    scanf("%d%lf", &num[i], &t);
  }
  solve(m);
}
