다코는 수십억개의 손가락을 가진 새로운 종류의 외계인 친구다. 이 친구가 기타를 잡더니 즉석에서 간단한 멜로디를 발견했다. 그리고 연주하기 시작 했다.

보통의 기타처럼 1 에서 6 번 번호로 표시되는 6 개의 줄이고 각 줄은 1 에서 P 번으로 표시되는 풀렛으로 나뉘어진다.

멜로디는 일련의 톤이다. 각 톤은 어떤 줄의 어떤 플렛을 누르면 발생한다(예를 들어 4 번 줄의 8 번 플렛을). 어떤 줄에서 여러개의 플렛이 눌려 진다면 가장 높은 플렛만이 영향을 미친다.

예를 들어 , 3 번째줄 5 번 풀렛이 먼저 눌러 진 상태에서 7 번 플렛에 해당하는 톤을 생성해야 한다면 다른 플렛을 릴리스 없이 7 번 플렛을 누를 수 있다. 왜냐하면 단지 가장 높은 것이 톤에 영향을 주기때문

마찬가지로 , 같은 줄위에 2 번째 플렛에 대응하는 톤은 5 번톤과 7 번톤을 릴리스후(5 번과 7 번이 눌러져 있는 경우)에 눌러야 한다.

1 번 입출력예에서

5 15 .. 5 개의 톤과 15 개의 플렛이 존재
2 8
2 10
2 12
2 10
2 5

• 8 누르고
• 10 누르고
• 12 누르고
• 12 번 릴리스(풀고) .. 그러면 10 톤이 발생
• 10 릴리스
• 8 릴리스
• 5 누르고

주어진 멜로디를 만들기 위해서 손각락의 최소 움직임 수를 구하시오. 싱글 플렛을 누르거나 릴리스하는 것은 한 번의 움직임으로 간주한다.

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.

출력

입출력 예

input

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

output

7

input

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

output

9

Second sample description: 1, 1, 1, 1, 3, 0, 2 finger movements are necessary, in the order of the seven tones produced.

출처:coci