CSHOWB - Sir and the Guitar


After teaching guitar to Jimmy Page (Led Zeppelin Band Guitarist), Sir Jadeja has decided to do something new. Sir Jadeja took out his guitar and started playing a melody he composed when he was 2 months old.

The guitar as usual has 6 strings denoted by numbers through 1 to 6. Each string is divided into P frets denoted by numbers 1 to P. A melody is a sequence of tones, where each tone is produced by picking a string pressed on a specific fret (for example: 4th string pressed on 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. If a tone that corresponds to the 2nd fret on the same string is to be produced next, it is necessary to release both 5th and 7th frets and only then press 2nd.

Sir Jadeja feeling tired wants to play the melody with minimum number of finger movements. Note that press or release a single fret counts as one finger move. String picking is not a finger move, but rather a guitar pick move and should not be counted. Remember that picking a string with not affect frets being pressed on other string. You can assume that Sir Jadeja has enough fingers to press all the frets on all string at the same time (yes, that many).

Input:

First line contains two integers: N (N <= 500000) and P (2 <= P <= 300000). N denotes number of tones in the melody and P denotes number of frets. The next N lines describe the fields for the corresponding tones: the number of the string and the number of the fret, respectively. Tones must be played in the order they are described.

Output:

Print a single integer: minimum number of finger movements that need to be made.

Examples

Input 1:
5 15 
2 8 
2 10 
2 12 
2 10 
2 5 

Output 1:
7
Input 2:
8 15 
2 8 
2 10 
2 12
3 7 
2 10
3 5 
2 5
3 3

Output 2:
12

Explanation:

For set 1: All the tones played 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 fifth fret is pressed followed by the release of frets 10 and 12( 5th, 6th and 7th ).


hide comments
mag1x_: 2018-05-23 19:26:58

Don't worry about 6 strings. Just think for all the cases of single string. :)

trijeet: 2017-10-28 09:40:13

A good problem for stacks. AC in 1 !

siddharth: 2016-04-27 00:02:48

@rishav goyal can you provide me with some test cases as I am getting NZEC using java.

Rishav Goyal: 2015-08-21 09:43:05

@mitch, please move this to tutorial.

Rishav Goyal: 2015-08-21 09:42:34

i would not call this one even easy


Added by:Aradhya
Date:2013-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeShow IIIT Allahabad