package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, m int
	if _, err := fmt.Fscan(r, &n, &m); err != nil {
		return
	}

	dp := make([]int, m+1)
	maxDp := 0

	for i := 0; i < n; i++ {
		var s int
		var x string
		fmt.Fscan(r, &s, &x)

		curMax := 0
		for j := 1; j <= s; j++ {
			if dp[j] > curMax {
				curMax = dp[j]
			}
		}
		dp[s] = curMax + 1
		if dp[s] > maxDp {
			maxDp = dp[s]
		}
	}

	fmt.Println(n - maxDp)
}