#include <bits/stdc++.h>
using namespace std;
inline int D() {
  int t;
  scanf("%d", &t);
  return t;
}
inline long long LLD() {
  long long t;
  scanf("%lld", &t);
  return t;
}
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double pi = 3.14159265359;
void file() {}
const int N = 5009;
int n, m, mem[N][N], a[N];
int solve(int ind, int sp) {
  if (ind == n) return 0;
  if (mem[ind][sp] != -1) return mem[ind][sp];
  int ret;
  if (a[ind] == sp)
    ret = solve(ind + 1, sp);
  else if (a[ind] > sp)
    ret = min(solve(ind + 1, a[ind]), 1 + solve(ind + 1, sp));
  else
    ret = 1 + solve(ind + 1, sp);
  return mem[ind][sp] = ret;
}
int main() {
  n = D(), m = D();
  for (int i = 0; i < n; i++) {
    a[i] = D();
    double d;
    cin >> d;
  }
  memset(mem, -1, sizeof mem);
  cout << solve(0, 1);
}
