Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.


-----Input-----

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species. Each of the following n lines contain two space-separated numbers: one integer number s_{i} (1 ≤ s_{i} ≤ m), and one real number x_{i} (0 ≤ x_{i} ≤ 10^9), the species and position of the i-th plant. Each x_{i} will contain no more than 6 digits after the decimal point.

It is guaranteed that all x_{i} are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their x_{i} coordinates (x_{i} < x_{i} + 1, 1 ≤ i < n).


-----Output-----

Output a single integer — the minimum number of plants to be replanted.


-----Examples-----
Input
3 2
2 1
1 2.0
1 3.100

Output
1

Input
3 3
1 5.0
2 5.5
3 6.0

Output
0

Input
6 3
1 14.284235
2 17.921382
1 20.328172
3 20.842331
1 25.790145
1 27.204125

Output
2



-----Note-----

In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

Difficulty: competition

Starter code:

Solutions:
n, m = map(int, input().split())
t = [int(input().split()[0]) for i in range(n)]
p = [0] * (m + 1)
for i, j in enumerate(t): p[j] = min(p[j], min(p[: j])) - 1
print(n + min(p))

from bisect import bisect_right
n = int(input().split()[0])
t = [int(input().split()[0]) for i in range(n)]
p, k = [], 0
for i in t:
    x = bisect_right(p, i)
    if x < k: p[x] = i
    else:
        p.append(i)
        k += 1
print(n - k)

n, m = map(int, input().split())
t = [int(input().split()[0]) for i in range(n)]
p = [0] * (m + 1)
for i, j in enumerate(t): p[j] = min(p[j], min(p[: j])) - 1
print(n + min(p))

numbers, types = list(map(int, input().split()))

position = [0] * (numbers)
binary_search_array = [1] * (numbers)

for i in range(numbers):
    position[i] = int(input().split()[0])

max_length = int(0)

for i in range(numbers):
    low = int(0)
    high = int(max_length)

    while (low < high):
        mid = int((low + high) / 2)
        if (binary_search_array[mid] <= position[i]):
            low = mid + 1
        else:
            high = mid

    binary_search_array[low] = position[i]
    if (low == max_length):
        max_length += 1


print(numbers - max_length)


'''n, m, k = [int(x) for x in input().split()]

trees = tuple([int(x) for x in input().split()])

costs = []
for x in range(n):
    costs.append([0] + [int(x) for x in input().split()])

dp = [[[float('inf') for z in range(m + 1)] for y in range(k + 1)] for x in range(n)]

if trees[0] == 0:
    for k in range(len(dp[0][0])):
        dp[0][1][k] = cost[0][k]
else:
    dp[0][0][trees[0]] = cost[0][trees[0]]

for i in range(1, len(dp)):
    for j in range(1, len(dp[0])):
        for k in range(1, len(dp[0][0])):
            if trees
            for l in range(len(dp[0][0])):
                if k == l:
                    dp[i][j][k] = dp[i - 1][j][k] + cost[i][k]
                else:
                    dp[i][j][k] = dp[i - 1][j - 1][l] + cost[i][k]'''



n, m = [int(x) for x in input().split()]
plant = [int(input().split()[0]) for x in range(n)]
dp = [1 for x in range(n)]



for i in range(len(plant)):
    for j in range(0, i):
        if plant[j] > plant[i]:
            continue
        dp[i] = max(dp[i], dp[j] + 1)
#print(dp)
print(n - max(dp))





'''for i in range(1, n):
    for k in range(plant[i], 0, -1):
        dp[plant[i]] = max(dp[plant[i]], 1 + dp[k])
print(n - max(dp) - 1)'''
    





























































n, m = map(int, input().split())
type = [0]
for x in range(n):
	type.append(int(input().split()[0]))

dp = [[0] * (m + 1) for x in range(2)]
for i in range(1, n + 1):
	dp[i & 1][0] = 1e9
	for j in range (1, m + 1):
		if type[i] == j:
			dp[i & 1][j] = dp[1 - (i & 1)][j]
		elif type[i] > j:
			dp[i & 1][j] = 1 + dp[1 - (i & 1)][j]
		else:
			if j >= 1:
				dp[i & 1][j] = min(dp[i & 1][j - 1], 1 + dp[1 - (i & 1)][j])
			else:
				dp[i & 1][j] = dp[1 - (i & 1)][j]
print (dp[n & 1][m])

n, m = list(map(int, input().split()))

t = [int(input().split()[0]) for i in range(n)]

p = [0] * (m + 1)

for i, j in enumerate(t): p[j] = min(p[j], min(p[: j])) - 1

print(n + min(p))



# Made By Mostafa_Khaled


n, m = list(map(int, input().split()))
t = [int(input().split()[0]) for i in range(n)]
p = [0] * (m + 1)
for i in t: p[i] = max(p[1:i+1])+1
print(n - max(p))


n, m = list(map(int, input().split()))
t = [int(input().split()[0]) for i in range(n)]
p = [0] * (m + 1)
for i, j in enumerate(t): p[j] = min(p[: j+1]) - 1
print(n + min(p))


n, m = [int(x) for x in input().split()]
d = [0 for i in range(m)]
for i in range(n):
    c, x = [x for x in input().split()]
    c = int(c)

    d[c-1] = max(d[:c])+1
print(n-max(d))
        


def CeilIndex(A, l, r, key): 
  
    while (r - l > 1): 
      
        m = l + (r - l)//2
        if (A[m] > key): 
            r = m 
        else: 
            l = m 
    return r 
   
def LongestIncreasingSubsequenceLength(A, size): 
  
    # Add boundary case, 
    # when array size is one 
   
    tailTable = [0 for i in range(size + 1)] 
    len = 0 # always points empty slot 
   
    tailTable[0] = A[0] 
    len = 1
    for i in range(1, size): 
      
        if (A[i] < tailTable[0]): 
  
            # new smallest value 
            tailTable[0] = A[i] 
   
        elif (A[i] >= tailTable[len-1]): 
  
            # A[i] wants to extend 
            # largest subsequence 
            tailTable[len] = A[i] 
            len+= 1
   
        else: 
            # A[i] wants to be current 
            # end candidate of an existing 
            # subsequence. It will replace 
            # ceil value in tailTable 
            tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i] 
          
   
    return len
  
# driver code 
arr = [] 
n,m=list(map(int,input().split()))
for i in range(n) :
    a,b=list(map(float,input().split()))
    arr.append(a)
   
print(n-LongestIncreasingSubsequenceLength(arr, n)) 
  
# This code is contributed 
# by Anant Agarwal. 


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/10/20

LIS

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(N, M, A):
    
    bit = [0 for _ in range(N)]
    
    def add(index, val):
        while index < N:
            bit[index] = max(bit[index], val)
            index |= index + 1
    
    def query(index):
        s = 0
        while index >= 0:
            s = max(s, bit[index])
            index = (index & (index + 1)) - 1
        
        return s
    
    q = [(v, i) for i, v in enumerate(A)]
    q.sort()
    
    s = 0
    for v, i in q:
        t = query(i) + 1
        add(i, t)
        s = max(s, t)
    
    return N-s
    
    
    


N, M = map(int, input().split())
A = []
for i in range(N):
    x, y = input().split()
    A.append(int(x))

print(solve(N, M, A))

def solve(n, a):
    lis = [0] * n
    for i in range(0, n):
        for j in range(0, i):
            if a[i] >= a[j]:
                lis[i] = max(lis[i], lis[j] + 1)
        if lis[i] == 0:
            lis[i] = 1
    print(n - max(lis))


def main():
    inp = lambda: int(input().split()[0])
    n = inp()
    a = [inp() for _ in range(n)]
    solve(n, a)


def __starting_point():
    main()


__starting_point()

# Basta encontrar la medida del mayor subarray que es no-decreciente.
# Con cada inserción podemos aumentar este número en 1.

n = int(input().split()[0])
a = []
for _ in range(n):
    a.append(int(input().split()[0]))
dp = [0]*n
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] <= a[i] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1
print(n - max(dp))



import math
import sys
input=sys.stdin.readline
#t=int(input())
t=1
for _ in range(t):
    #n=int(input())
    n,m=list(map(int,input().split()))
    #l=list(map(int,input().split()))
    l=[]
    for __ in range(n):
        s,x=list(map(float,input().split()))
        l.append(int(s))
    dp=[0]*(n+1)
    for i in range(n):
        j=l[i]
        for j1 in range(j,-1,-1):
            dp[j]=max(dp[j],1+dp[j1])
    maxi=max(dp[:])
    print(n-maxi)



n,m = list(map(int,input().split()))
arr = []
for i in range(n):
    l = list(map(float,input().split()))
    arr.append(int(l[0]))
dp = [1 for i in range(n)]

for i in range(1,n):
    for j in range(i):
        if arr[j]<=arr[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(n-max(dp))

from math import ceil,sqrt
from collections import defaultdict




def solve():


    n,m = list(map(int,input().split()))

    l = []
    for i in range(n):
        a,b = list(map(float,input().split()))
        l.append(a)

    dp = [0]*(n)

    for i in range(n):
        maxi = 0
        for j in range(i):
           if l[i]>=l[j]:
             maxi = max(dp[j],maxi)

        dp[i] = maxi+1
    # print(dp)
    print(n-max(dp))















# t = int(input())
# for _ in range(t):

solve()




n,m=map(int,input().split())
l=[]
for i in range(n):
	a,b=input().split()
	l.append(int(a))
dp=[1]*n
for i in range(1,n):
	for j in range(0,i):
		if l[i]>=l[j]:	
			dp[i]=max(dp[i],dp[j]+1)
print(n-max(dp))