외계인의 기타 연주

손가락이 아주 많은 외계인이 기타로 주어진 멜로디를 연주하려고 한다.

기타에는 1번부터 6번까지 모두 6개의 줄이 있고, 각 줄에는 1번부터 P번까지의 프렛이 있다. 하나의 음은 특정 줄의 특정 프렛을 누른 뒤 그 줄을 튕기면 낼 수 있다. 같은 줄에서 여러 프렛을 동시에 누르고 있으면, 그중 번호가 가장 큰 프렛의 음이 난다.

예를 들어 3번 줄의 5번 프렛을 이미 누르고 있을 때 7번 프렛의 음을 내려면, 5번 프렛을 누른 손가락은 그대로 두고 다른 손가락으로 7번 프렛을 누르면 된다. 반대로 2번 프렛의 음을 내려면, 5번과 7번 프렛을 누르던 손가락을 모두 뗀 뒤 2번 프렛을 눌러야 한다.

프렛을 한 번 누르거나, 누르고 있던 프렛에서 손가락을 한 번 떼는 것을 손가락을 한 번 움직인 것으로 센다. 멜로디가 순서대로 주어질 때, 필요한 손가락 움직임의 최솟값을 구하라.

첫째 줄에 멜로디에 포함된 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 <= N <= 500,000, 2 <= P <= 300,000)

다음 N개 줄에는 각 음을 나타내는 두 정수 s와 f가 주어진다. s는 줄 번호이고, f는 그 줄에서 눌러야 하는 프렛 번호이다. 음은 입력으로 주어진 순서대로 연주해야 한다. 줄 번호는 1 이상 6 이하이고, 프렛 번호는 1 이상 P 이하이다.

멜로디를 연주하는 데 필요한 최소 손가락 움직임 횟수를 출력한다.