#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXVAL = 1e9 + 5;
int dp[2][MAXN];
int arr[MAXN];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j <= m; ++j) dp[i & 1][j] = MAXVAL;
  }
  vector<vector<int> > pos(m + 1);
  for (int i = 1; i <= n; ++i) {
    int type;
    float x;
    scanf("%d %f", &type, &x);
    pos[type].push_back(i);
    arr[i] = type;
  }
  int sum = 0;
  for (int i = 1; i <= m; ++i) {
    sum += pos[i - 1].size();
    dp[0 & 1][i] = sum;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int rem = upper_bound(pos[j - 1].begin(), pos[j - 1].end(), i) -
                pos[j - 1].begin();
      rem = pos[j - 1].size() - rem;
      dp[i & 1][j] =
          min(dp[i & 1 ^ 1][j], dp[i & 1][j - 1] + rem) + (arr[i] > j);
    }
  }
  printf("%d\n", dp[n & 1][m]);
  return 0;
}
