← 返回题目列表

Codeforces · 269/B

B. 温室效应

中文机器翻译题面 查看原题

Emuskald 是一位狂热的园艺家,拥有世界上最长的温室——它的长度实际上是无限的。

多年来,Emuskald 在他的温室中种植了 n 株植物,其中有 m 种不同的植物物种,编号从 1 到 m。他的温室非常狭窄,可以看作是一条无限的线,每株植物都占据该线上的一个点。

Emuskald 发现每个物种在不同的温度下茁壮成长,因此他想要布置 m - 1 个边界,将温室分为 m 个部分,从左到右编号为 1 到 m,每个部分容纳一个物种。他可以自由地放置边界,但最终所有第 i 种植物都必须位于左侧的第 i 个区域中。

当然,并不总是能够以这种方式放置边界,因此 Emuskald 需要重新种植一些植物。他可以将每株植物从其位置移走,并将其放置在温室中的任何位置(任何实际坐标),而其中没有任何植物。由于重新种植会给植物带来很大的压力,因此请帮助埃穆斯卡德找到他必须重新种植才能放置边界的最少植物数量。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 5000, n ≥ m),植物的数量和不同物种的数量。以下 n 行中的每一行包含两个以空格分隔的数字:一个整数 si (1 ≤ si ≤ m) 和一个实数 xi (0 ≤ xi ≤ 109),即第 i 株植物的种类和位置。每个 xi 小数点后不超过 6 位数字。

保证所有xi都不同;每个物种至少有一种植物;植物按“从左到右”的顺序给出,即按其 xi 坐标的升序排列 (xi < xi + 1, 1 ≤ i < n)。

输出

输出一个整数——需要重新种植的植物的最小数量。

示例

输入 #1

3 2
2 1
1 2.0
1 3.100

输出 #1

1

输入 #2

3 3
1 5.0
2 5.5
3 6.0

输出 #2

0

输入 #3

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

输出 #3

2

注意

在第一个测试用例中,Emuskald 可以将第一株植物重新种植到最后一株植物的右侧,因此答案为 1。

在第二个测试用例中,物种的顺序已经正确,因此不需要重新种植。