#include <bits/stdc++.h>
using namespace std;
struct edge {
  int x;
  double point;
  bool operator<(const edge& p) const { return point < p.point; }
};
int dp[5003][5003], ara[5003][5003];
int take[5003], n, m;
int dp_func(int pos, int val) {
  if (val == m + 1) {
    return 0;
  }
  if (pos == n + 1) {
    return 0;
    return 16000;
  }
  int ret = 16000;
  if (dp[pos][val] != -1) return dp[pos][val];
  if (take[pos] == val) {
    ret = min(ret, dp_func(pos + 1, val + 1) + ara[val][pos + 1]);
  }
  if (take[pos] > val) {
    ret = min(ret, dp_func(pos + 1, val) + 1);
    ret = min(ret, dp_func(pos, val + 1) + ara[val][pos + 1]);
  }
  if (take[pos] <= val) ret = min(ret, dp_func(pos + 1, val));
  return dp[pos][val] = ret;
}
int main() {
  int i, j, k, l;
  double a, b, c, d, f;
  cin >> n >> m;
  for (i = 1; i <= n; i++) {
    scanf("%d%lf", &take[i], &a);
  }
  memset(ara, 0, sizeof ara);
  for (i = 1; i <= m; i++) {
    for (j = n; j >= 1; j--) {
      if (take[j] == i)
        ara[i][j] = ara[i][j + 1] + 1;
      else
        ara[i][j] = ara[i][j + 1];
    }
  }
  memset(dp, -1, sizeof dp);
  cout << dp_func(1, 1) << endl;
}
