레이팅 미적용Darko has a new imaginary extraterrestrial friend with a billion fingers. The extraterrestrial soon took hold of his guitar, found a simple melody online, and started playing it.
The guitar, as usual, has six strings denoted by numbers \(1\) through \(6\). Each string is divided into \(P\) frets denoted by numbers \(1\) through \(P\).
A melody is a sequence of tones, where each tone is produced by picking a string pressed on a specific fret (e.g. the 4th string pressed on the 8th fret). If a string is pressed on several frets, the produced tone will be the one corresponding to the highest of those frets.
For instance, if the 3rd string is already pressed on the 5th fret, and the tone which corresponds to the 7th fret is to be produced, the string can be pressed on the 7th fret and picked without releasing the 5th fret, since only the highest one affects the tone produced (7th in this case). Similarly, if a tone that corresponds to the 2nd fret on the same string is next to be produced, it is necessary to release both the 5th and 7th frets.
Write a program which computes the minimum number of finger movements needed to produce the given melody. Note that pressing or releasing a single fret counts as one finger move. String picking does not count as a finger move.
The first line of input contains two positive integers separated by a single space, \(N\) (\(N \le 500\,000\)) and \(P\) (\(2 \le P \le 300\,000\)). They represent the number of tones in the melody and the number of frets, respectively.
The following \(N\) lines describe the tones — the ordinal of the string and the ordinal of the fret, respectively, in the same order as the extraterrestrial plays them.
In a single line of output, print the minimum number of finger movements.
First sample description: all the tones are produced by picking the 2nd string. First, the frets \(8\), \(10\), \(12\) are pressed, in order (three movements). Then, the 12th fret is released to produce the second tone again (fourth movement). Finally, the 5th fret is pressed followed by the release of frets \(10\) and \(12\) (a total of seven movements).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Test 1 | 10점 | None |
Test 2 | 10점 | None |
Test 3 | 10점 | None |
Test 4 | 10점 | None |
Test 5 | 10점 | None |
Test 6 | 10점 | None |
Test 7 | 10점 | None |
Test 8 | 10점 | None |
Test 9 | 10점 | None |
Test 10 | 10점 | None |
5 15
2 8
2 10
2 12
2 10
2 577 15
1 5
2 3
2 5
2 7
2 4
1 5
1 39