#include <bits/stdc++.h>
using namespace std;
int main() {
  int plantsCount, speciesCount;
  scanf("%d %d", &plantsCount, &speciesCount);
  vector<int> plants;
  for (int i = 0; i < plantsCount; ++i) {
    int plant;
    double tmp;
    scanf("%d %lf", &plant, &tmp);
    plants.push_back(plant - 1);
  }
  vector<vector<int>> dp(plantsCount + 1);
  for (int i = 0; i < plantsCount + 1; ++i) {
    dp[i].resize(speciesCount);
  }
  for (int i = 1; i < plantsCount + 1; ++i) {
    for (int j = 0; j < speciesCount; ++j) {
      if (plants[i - 1] == j) {
        for (int k = 0; k <= j; ++k) {
          dp[i][j] = max(dp[i][j], dp[i - 1][k]);
        }
        dp[i][j]++;
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  int maxLength = 0;
  for (int i = 0; i < speciesCount; ++i) {
    maxLength = max(maxLength, dp[plantsCount][i]);
  }
  printf("%d", plantsCount - maxLength);
}
