문제

Author: Adrian Satja Kurdija

Darko has a new imaginary extraterrestrial friend with a billion of fingers. The extraterrestrial has 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. 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 5th and 7th frets. Write a program which computes the minimum number of finger movements needed to produce the given melody. Note that press or release a single fret counts as one finger move. String picking does not count as finger move, but rather a guitar pick move.

입력

The first line of input contains two positive integers separated by a single space, N (N ≤ 500 000) and P (2 ≤ P ≤ 300 000). They represent the number of tones in the melody and the number of frets, respectively. The following N lines describe the fields for the corresponding tones – the ordinal of the string and the ordinal of the fret, respectively, in the same order as the extraterrestrial play them.

출력

In a single line of output, print the minimum number of finger movements. Author: Adrian Satja Kurdija

예제 입력 1

5 15
2 8
2 10
2 12
2 10
2 5

예제 출력 1

7

예제 입력 2

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

예제 출력 2

9