#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int inf = 0x3f3f3f3f;
struct node {
  int s, id;
} w[N];
int dp[N][N];
bool cmp(const node &a, const node &b) {
  if (a.s != b.s) return a.s < b.s;
  return a.id < b.id;
}
int main() {
  int n, m;
  double x;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    cin >> w[i].s >> x;
    w[i].s--;
    w[i].id = i;
  }
  sort(w, w + n, cmp);
  memset(dp, 0, sizeof(dp));
  dp[0][w[0].id] = 1;
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < n; ++j) dp[i][j] = dp[i - 1][j];
    for (int j = 0; j <= w[i].id; ++j)
      dp[i][w[i].id] = max(dp[i][w[i].id], dp[i - 1][j] + 1);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) ans = max(ans, dp[n - 1][i]);
  cout << n - ans << endl;
  return 0;
}
