#include <bits/stdc++.h>
using namespace std;
const long long OO = 0x0101010101010101;
class debug_t {
 public:
  template <typename T>
  debug_t& operator<<(const T& o) {
    return *this;
  }
} dout;
int n, m;
vector<pair<int, double>> vec;
int dp[5005][5005];
int solve(int idx, int last_idx) {
  if (idx > n) return 0;
  int& ret = dp[idx][last_idx];
  if (ret + 1) return ret;
  ret = 0;
  int type = vec[idx].first;
  double x = vec[idx].second;
  int sol1, sol2;
  sol1 = sol2 = 1e8;
  if (x > vec[last_idx].second) sol1 = solve(idx + 1, idx);
  sol2 = 1 + solve(idx + 1, last_idx);
  return ret = min(sol1, sol2);
}
int main() {
  memset(dp, -1, sizeof dp);
  cin >> n >> m;
  vec.push_back({0, -1e8});
  for (int i = 1; i <= n; i++) {
    int t;
    double x;
    cin >> t >> x;
    vec.push_back({t, x});
  }
  sort(vec.begin(), vec.end());
  cout << solve(1, 0);
  dout << "\nExecution Time = " << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
}
