#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 998244353;
const int64_t INF = 1e18;
const int64_t eps = 1e-18;
void io(string s1 = "input.txt", string s2 = "output.txt") {
  freopen(s1.c_str(), "r", stdin);
  freopen(s2.c_str(), "w", stdout);
}
const int64_t N = 2e5 + 5;
int64_t dp[N], v[N];
int64_t n, m;
int64_t tree[4 * N];
int64_t get(int64_t s, int64_t e, int64_t idx, int64_t S, int64_t E) {
  if (s > E || e < S) return -INF;
  if (s >= S && e <= E) return tree[idx];
  int64_t mid = (s + e) / 2;
  return max(get(s, mid, idx * 2, S, E), get(mid + 1, e, idx * 2 + 1, S, E));
}
void update(int64_t s, int64_t e, int64_t idx, int64_t SE, int64_t val) {
  if (SE > e || SE < s) return;
  if (s == e) {
    tree[idx] = max(val, tree[idx]);
    return;
  }
  int64_t mid = (s + e) / 2;
  update(s, mid, idx * 2, SE, val);
  update(mid + 1, e, idx * 2 + 1, SE, val);
  tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  cin >> v[0];
  long double d;
  cin >> d;
  dp[0] = 1;
  update(1, m, 1, v[0], dp[0]);
  for (int64_t i = 1; i < n; i++) {
    cin >> v[i];
    long double d;
    cin >> d;
    dp[i] = 1 + get(1, m, 1, 1, v[i]);
    update(1, m, 1, v[i], dp[i]);
  }
  cout << n - *max_element(dp, dp + n);
}
