#include <bits/stdc++.h>
namespace solution {
class SolutionInterface {
 public:
  virtual int run() = 0;

 protected:
  virtual void pre_calc() {}
  virtual bool action() = 0;
  virtual void init(){};
  virtual bool input() { return false; };
  virtual void output(){};
  SolutionInterface() {}

 private:
};
}  // namespace solution
namespace solution {
class SolutionBase : public SolutionInterface {
 public:
  virtual int run() {
    pre_calc();
    while (action())
      ;
    return 0;
  }
};
}  // namespace solution
namespace solution {}
namespace solution {
using namespace std;
}
namespace solution {
const int SIZE = 5000 + 11;
const int NONE = std::numeric_limits<int>::min();
int n, m;
int A[SIZE];
double B[SIZE];
int result;
int dp[SIZE];
}  // namespace solution
namespace solution {
class Solver {
 public:
  void solve() { result = get_maximum_length(); }
  int get_maximum_length() {
    A[0] = 0;
    for (int i = 0; i < SIZE; ++i) dp[i] = NONE;
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int k = 0;
      for (int j = 0; j < i; ++j) {
        if (dp[j] == NONE) continue;
        if (A[j] <= A[i]) {
          if (dp[j] > dp[k]) {
            k = j;
          }
        }
      }
      dp[i] = dp[k] + 1;
    }
    return n - *max_element(dp, dp + n + 1);
  }

 private:
};
}  // namespace solution
namespace solution {
class Solution : public SolutionBase {
 public:
 protected:
  virtual bool action() {
    init();
    if (!input()) return false;
    solver.solve();
    output();
    return true;
  }
  bool input() {
    if (!(cin >> n >> m)) return false;
    for (int i = 1; i <= n; ++i) cin >> A[i] >> B[i];
    return true;
  }
  void output() { cout << result << endl; }

 private:
  Solver solver;
};
}  // namespace solution
int main() { return solution::Solution().run(); }
