Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Greenhouse Effect

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEmuskald 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 11:08:04 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|