#include <bits/stdc++.h>
using namespace std;
inline bool checkBit(long long n, int i) { return n & (1LL << i); }
inline long long setBit(long long n, int i) {
  return n | (1LL << i);
  ;
}
inline long long resetBit(long long n, int i) { return n & (~(1LL << i)); }
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
inline bool EQ2(double a, double b) { return fabs(a - b) < 1e-7; }
int tree[100 * 5100], n, m;
void update(int node, int l, int r, int target, int val) {
  if (l == r && r == target) {
    tree[node] = val;
    return;
  }
  if (l > target || r < target) return;
  int mid = (l + r) / 2;
  update(node * 2, l, mid, target, val);
  update(node * 2 + 1, mid + 1, r, target, val);
  tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
  return;
}
int query(int node, int l, int r, int b, int e) {
  if (l >= b && r <= e) return tree[node];
  if (l > e || r < b) return -100000000;
  int mid = (l + r) / 2;
  int p = query(node * 2, l, mid, b, e);
  int q = query(node * 2 + 1, mid + 1, r, b, e);
  return max(p, q);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int ans = 0;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    int a;
    double b;
    cin >> a >> b;
    --a;
    int temp = query(1, 0, n - 1, 0, a);
    ans = max(ans, temp + 1);
    update(1, 0, n - 1, a, temp + 1);
  }
  cout << n - ans;
  return 0;
}
