#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 5005
int n, m, type[MAXN], dp[MAXN];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
double x;
scanf("%d %lf", type+i, &x);
}
for(int i = 1; i <= n; i++) {
int j = type[i];
for(int k = j; k >= 1; k--) {
dp[j] = max(dp[j], 1+dp[k]);
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
printf("%d\n", n-ans);
}
I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgTUFYTiA1MDA1CgppbnQgbiwgbSwgdHlwZVtNQVhOXSwgZHBbTUFYTl07CgppbnQgbWFpbigpIHsgICAgCglzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwoJZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKCQlkb3VibGUgeDsKCQlzY2FuZigiJWQgJWxmIiwgdHlwZStpLCAmeCk7Cgl9CgkKCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CgkJaW50IGogPSB0eXBlW2ldOwoJCWZvcihpbnQgayA9IGo7IGsgPj0gMTsgay0tKSB7CgkJCWRwW2pdID0gbWF4KGRwW2pdLCAxK2RwW2tdKTsKCQl9Cgl9CgkKCWludCBhbnMgPSAwOwoJZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKCQlhbnMgPSBtYXgoYW5zLCBkcFtpXSk7Cgl9CglwcmludGYoIiVkXG4iLCBuLWFucyk7Cn0K