#include <bits/stdc++.h>
using namespace std;
int m[2][5110];
int lcs(vector<int> s1, vector<int> s2) {
  memset(m, 0, sizeof(m));
  int N = ((int)(s1.size())), M = ((int)(s2.size())), i, j, ii;
  for (i = M; i >= 0; i--) {
    ii = i & 1;
    for (j = N; j >= 0; j--) {
      if (i == M || j == N) {
        m[ii][j] = 0;
        continue;
      }
      if (s1[i] == s2[j])
        m[ii][j] = 1 + m[1 - ii][j + 1];
      else
        m[ii][j] = max(m[ii][j + 1], m[1 - ii][j]);
    }
  }
  return m[0][0];
}
int n, M, t1;
double d;
int main() {
  ios_base::sync_with_stdio(0);
  vector<int> v;
  cin >> n >> M;
  for (int i(0), _n(n); i < _n; ++i) {
    cin >> t1 >> d;
    v.push_back(t1);
  }
  vector<int> v1 = v;
  sort(v1.begin(), v1.end());
  cout << n - lcs(v, v1);
}
