시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1946 746 616 38.913%

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이 때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

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

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력 1

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

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjI4NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NTggXHVhZTMwXHVkMGMwIFx1YzVmMFx1YzhmYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzBjMVx1YzBjMVx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzQwIFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWMyMThcdWMyZWRcdWM1YjVcdWFjMWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViMjkwXHViMGEwIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBcdWFlMzBcdWQwYzBcdWFjMDAgXHVjZTU4XHVhY2UwIFx1YzJmNlx1YzVjOFx1YWNlMCwgXHVjNzc4XHVkMTMwXHViMTM3XHVjNWQwXHVjMTFjIFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWJhNWNcdWI4NWNcdWI1MTRcdWI5N2MgXHVhYzgwXHVjMGM5XHVkNTg4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzc0IFx1YWUzMFx1ZDBjMFx1Yjk3YyBcdWNlNThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjZjRcdWQxYjUgXHVhZTMwXHVkMGMwXHViMjk0IDFcdWJjODggXHVjOTA0XHViZDgwXHVkMTMwIDZcdWJjODggXHVjOTA0XHVhZTRjXHVjOWMwIFx1Y2QxZCA2XHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWM5MDRcdWM3NDAgUFx1YWMxY1x1Yzc1OCBcdWQ1MDRcdWI4MWJcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVkNTA0XHViODFiXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjNjNCAxXHViYzg4XHViZDgwXHVkMTMwIFBcdWJjODhcdWFlNGNcdWM5YzAgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTVjXHViODVjXHViNTE0XHViMjk0IFx1Yzc0Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWM3NGNcdWM3NDAgXHVjOTA0XHVjNWQwXHVjMTFjIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc0XHVhY2UwIFx1YzkwNFx1Yzc0NCBcdWQyOTVcdWFlMzBcdWJhNzQgXHVjNWYwXHVjOGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDRcdWJjODggXHVjOTA0XHVjNzU4IDhcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWQyOTVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM1YjRcdWI1YTQgXHVjOTA0XHVjNzU4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVkNTA0XHViODFiXHVjNzU4IFx1Yzc0Y1x1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDNcdWJjODggXHVjOTA0XHVjNzU4IDVcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1Yzc3NFx1YmJmOCBcdWIyMDRcdWI5NzRcdWFjZTAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgN1x1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWJhNzQsIDVcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWMxOTBcdWM3NDQgXHViNWJjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWIyZTRcdWI5NzggXHVjMTkwXHVhYzAwXHViNzdkXHVjNzNjXHViODVjIDdcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM5MDRcdWM3NDQgXHVkMjk1XHVhZTMwXHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzU4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0XHViYTc0LCA1XHViYzg4XHVhY2ZjIDdcdWJjODhcdWM3NDQgXHViMjA0XHViOTc0XHViMzU4IFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWI1YzAgXHViMmU0XHVjNzRjXHVjNWQwIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM1ZjBcdWM4ZmNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjMTkwXHVhYzAwXHViNzdkXHVjNzNjXHViODVjIFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YjIwNFx1Yjk3NFx1YWM3MFx1YjA5OCBcdWI1YmNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1YzYwMFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWJhNWNcdWI4NWNcdWI1MTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTkwXHVhYzAwXHViNzdkXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYTVjXHViODVjXHViNTE0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjNzRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChOICZsZTsgNTAwLDAwMCwgMiAmbGU7IFAgJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYTVjXHViODVjXHViNTE0XHVjNzU4IFx1ZDU1YyBcdWM3NGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM5MDRcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IFx1YWRmOCBcdWM5MDRcdWM1ZDBcdWMxMWMgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4MWJcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc0Y1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhZTMwXHVkMGMwXHViOTdjIFx1YzVmMFx1YzhmY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhNWNcdWI4NWNcdWI1MTRcdWI5N2MgXHVjNWYwXHVjOGZjXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMTkwXHVhYzAwXHViNzdkIFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdJVEFSQSIsImRlc2NyaXB0aW9uIjoiPHA+RGFya28gaGFzIGEgbmV3IGltYWdpbmFyeSBleHRyYXRlcnJlc3RyaWFsIGZyaWVuZCB3aXRoIGEgYmlsbGlvbiBvZiBmaW5nZXJzLiBUaGUgZXh0cmF0ZXJyZXN0cmlhbCBoYXMgc29vbiB0b29rIGhvbGQgb2YgaGlzIGd1aXRhciwgZm91bmQgYSBzaW1wbGUgbWVsb2R5IG9ubGluZSwgYW5kIHN0YXJ0ZWQgcGxheWluZyBpdC48XC9wPlxyXG5cclxuPHA+VGhlIGd1aXRhciwgYXMgdXN1YWwsIGhhcyBzaXggc3RyaW5ncyBkZW5vdGVkIGJ5IG51bWJlcnMgMSB0aHJvdWdoIDYuIEVhY2ggc3RyaW5nIGlzIGRpdmlkZWQgaW50byBQIGZyZXRzIGRlbm90ZWQgYnkgbnVtYmVycyAxIHRocm91Z2ggUC48XC9wPlxyXG5cclxuPHA+QSBtZWxvZHkgaXMgYSBzZXF1ZW5jZSBvZiB0b25lcywgd2hlcmUgZWFjaCB0b25lIGlzIHByb2R1Y2VkIGJ5IHBpY2tpbmcgYSBzdHJpbmcgcHJlc3NlZCBvbiBhIHNwZWNpZmljIGZyZXQgKGUuZy4gNHRoIHN0cmluZyBwcmVzc2VkIG9uIHRoZSA4dGggZnJldCkuIElmIGEgc3RyaW5nIGlzIHByZXNzZWQgb24gc2V2ZXJhbCBmcmV0cywgdGhlIHByb2R1Y2VkIHRvbmUgd2lsbCBiZSB0aGUgb25lIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGhpZ2hlc3Qgb2YgdGhvc2UgZnJldHMuPFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgaWYgdGhlIDNyZCBzdHJpbmcgaXMgYWxyZWFkeSBwcmVzc2VkIG9uIHRoZSA1dGggZnJldCwgYW5kIHRoZSB0b25lIHdoaWNoIGNvcnJlc3BvbmRzIHRvIHRoZSA3dGggZnJldCBpcyB0byBiZSBwcm9kdWNlZCwgdGhlIHN0cmluZyBjYW4gYmUgcHJlc3NlZCBvbiB0aGUgN3RoIGZyZXQgYW5kIHBpY2tlZCB3aXRob3V0IHJlbGVhc2luZyB0aGUgNXRoIGZyZXQsIHNpbmNlIG9ubHkgdGhlIGhpZ2hlc3Qgb25lIGFmZmVjdHMgdGhlIHRvbmUgcHJvZHVjZWQgKDd0aCBpbiB0aGlzIGNhc2UpLiBTaW1pbGFybHksIGlmIGEgdG9uZSB0aGF0IGNvcnJlc3BvbmRzIHRvIHRoZSAybmQgZnJldCBvbiB0aGUgc2FtZSBzdHJpbmcgaXMgbmV4dCB0byBiZSBwcm9kdWNlZCwgaXQgaXMgbmVjZXNzYXJ5IHRvIHJlbGVhc2UgYm90aCA1dGggYW5kIDd0aCBmcmV0cy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNvbXB1dGVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBmaW5nZXIgbW92ZW1lbnRzIG5lZWRlZCB0byBwcm9kdWNlIHRoZSBnaXZlbiBtZWxvZHkuIE5vdGUgdGhhdCBwcmVzcyBvciByZWxlYXNlIGEgc2luZ2xlIGZyZXQgY291bnRzIGFzIG9uZSBmaW5nZXIgbW92ZS4gU3RyaW5nIHBpY2tpbmcgZG9lcyBub3QgY291bnQgYXMgZmluZ2VyIG1vdmUsIGJ1dCByYXRoZXIgYSBndWl0YXIgcGljayBtb3ZlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgTiAoTiAmbGU7IDUwMCAwMDApIGFuZCBQICgyICZsZTsgUCAmbGU7IDMwMCAwMDApLiBUaGV5IHJlcHJlc2VudCB0aGUgbnVtYmVyIG9mIHRvbmVzIGluIHRoZSBtZWxvZHkgYW5kIHRoZSBudW1iZXIgb2YgZnJldHMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGRlc2NyaWJlIHRoZSBmaWVsZHMgZm9yIHRoZSBjb3JyZXNwb25kaW5nIHRvbmVzICZuZGFzaDsgdGhlIG9yZGluYWwgb2YgdGhlIHN0cmluZyBhbmQgdGhlIG9yZGluYWwgb2YgdGhlIGZyZXQsIHJlc3BlY3RpdmVseSwgaW4gdGhlIHNhbWUgb3JkZXIgYXMgdGhlIGV4dHJhdGVycmVzdHJpYWwgcGxheSB0aGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LCBwcmludCB0aGUgbWluaW11bSBudW1iZXIgb2YgZmluZ2VyIG1vdmVtZW50cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 3번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: wxogus25