#include <bits/stdc++.h>
using namespace std;
bool Check(int N, int pos) { return (bool)(N & (1 << pos)); }
int Set(int N, int pos) { return (N | (1 << pos)); }
long long BigMod(long long B, long long P, long long M) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) {
      R = (R * B) % M;
    }
    P /= 2;
    B = (B * B) % M;
  }
  return R;
}
int n, m;
vector<pair<double, int> > v;
int dp[5005][5005][2];
inline int call(int pos, int got, int stat) {
  if (got > m) return 10000;
  if (pos == n) {
    if (got == m)
      return 0;
    else
      return 10000;
  }
  if (dp[pos][got][stat] != -1) return dp[pos][got][stat];
  int ret = 0;
  int g = 0;
  if (v[pos].second != got and stat == 0) g = 1;
  ret = min(call(pos + 1, got, 0), call(pos, got + 1, 1));
  return dp[pos][got][stat] = ret + g;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  memset(dp, -1, sizeof(dp));
  cin >> n >> m;
  v.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].second >> v[i].first;
  }
  sort(v.begin(), v.end());
  int mx = 10000;
  for (int i = 0; i < m; i++) {
    mx = min(mx, call(0, i + 1, 0));
  }
  cout << mx;
}
