B. Теплица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Эмускальд — страстный садовод. В его владении находится самая длинная теплица в мире — ее длина практически бесконечна.

За многие годы Эмускальд вырастил n растений в своей теплице, каждое растение принадлежит одному из m различных видов, пронумерованных от 1 до m. Теплица Эмускальда очень узкая и ее можно рассматривать как бесконечную прямую, где каждое растение занимает одну точку на этой прямой.

Эмускальд обнаружил, что для каждого вида растений есть своя оптимальная температура. Теперь юноша хочет расставить m - 1 заслонок, которые разделили бы теплицу на m отделений, пронумерованных от 1 до m слева направо, так чтобы в каждом отделении росли все растения одного конкретного вида. Он может ставить заслонки так, как хочет, но в итоге каждое растение i-го вида должно произрастать в i-ом слева отделении теплицы.

Конечно, не всегда возможно расставить заслонки именно так, и Эмускальду придется пересадить некоторые свои растения. Он может пересадить каждое растение с изначального места в любое место в теплице (в любой вещественной координате), если там еще нет другого растения. Так как пересадка неблагоприятно сказывается на растениях, помогите Эмускальду найти минимальное количество растений, которое он должен пересадить, чтобы расставить заслонки требуемым образом.

Входные данные

В первой строке входных данных записаны через пробел два целых числа 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).

Выходные данные

Выведите единственное целое число — минимальное количество растений, которые надо пересадить.

Примеры
Входные данные
3 2
2 1
1 2.0
1 3.100
Выходные данные
1
Входные данные
3 3
1 5.0
2 5.5
3 6.0
Выходные данные
0
Входные данные
6 3
1 14.284235
2 17.921382
1 20.328172
3 20.842331
1 25.790145
1 27.204125
Выходные данные
2
Примечание

В первом тесте Эмускальд может пересадить первое растение справа от последнего растения, так что ответ равен 1.

Во втором тесте все виды уже растут в правильном порядке, так что ничего пересаживать не надо.