#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
const int mod = 1e9 + 7;
const ll inf = ll(1e18);
const double PI = acos(-1), eps = 1e-9;
const int mxn = 7e3, mxa = 1e5, mxk = 2e3;
int n, m, second[mxn], dp[mxn];
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    double x;
    cin >> second[i] >> x;
  }
  for (int i = 0; i < n; ++i) {
    dp[i] = 1;
    for (int j = 0; j < i; ++j) {
      if (second[i] >= second[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
  }
  int mx = *max_element(dp, dp + n);
  cout << n - mx << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  t = 1;
  while (t-- > 0) solve();
}
