#include <bits/stdc++.h>
using namespace std;
int dp[5010][5010];
vector<pair<int, double> > arr;
int n, m;
int solve(int idx, int box) {
  if (idx == n)
    return 0;
  else if (box == m + 1)
    return n + 10;
  else if (dp[idx][box] != -1)
    return dp[idx][box];
  int ret = solve(idx, box + 1);
  if (arr[idx].first != box)
    ret = min(ret, 1 + solve(idx + 1, box));
  else
    ret = min(ret, solve(idx + 1, box));
  return (dp[idx][box] = ret);
}
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = (int)(0); i < (int)(5010); i++)
    for (int j = (int)(0); j < (int)(5010); j++) dp[i][j] = -1;
  cin >> n >> m;
  arr.resize(n);
  for (int i = (int)(0); i < (int)(n); i++)
    cin >> arr[i].first >> arr[i].second;
  cout << solve(0, 1) << endl;
  return 0;
}
