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 \(4\)th string pressed on the \(8\)th 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 \(3\)rd string is already pressed on the \(5\)th fret, and the tone which corresponds to the \(7\)th fret is to be produced, the string can be pressed on the \(7\)th fret and picked without releasing the \(5\)th fret, since only the highest one affects the tone produced (\(7\)th in this case). Similarly, if a tone that corresponds to the \(2\)nd fret on the same string is next to be produced, it is necessary to release both the \(5\)th and \(7\)th 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 \(2\)nd string. First, the frets \(8\), \(10\), \(12\) are pressed, in order (three movements). Then, the \(12\)th fret is released to produce the second tone again (fourth movement). Finally, the \(5\)th fret is pressed followed by the release of frets \(10\) and \(12\) (a total of seven movements).

riseoj 작성

출처 COCI 2010/2011 Contest 7