시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3035 1230 984 40.328%

문제

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

보통 기타는 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+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzBjMVx1YzBjMVx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzQwIFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWMyMThcdWMyZWRcdWM1YjVcdWFjMWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NDAgXHVhZTMwXHVkMGMwXHVhYzAwIFx1Y2U1OFx1YWNlMCBcdWMyZjZcdWM1YzhcdWFjZTAsIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzVkMFx1YzExYyBcdWFjMDRcdWIyZThcdWQ1NWMgXHViYTVjXHViODVjXHViNTE0XHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU4OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1Yzc3NCBcdWFlMzBcdWQwYzBcdWI5N2MgXHVjZTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2Y0XHVkMWI1IFx1YWUzMFx1ZDBjMFx1YjI5NCAxXHViYzg4IFx1YzkwNFx1YmQ4MFx1ZDEzMCA2XHViYzg4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWNkMWQgNlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIFBcdWFjMWNcdWM3NTggXHVkNTA0XHViODFiXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIzYzQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBQXHViYzg4XHVhZTRjXHVjOWMwIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE1Y1x1Yjg1Y1x1YjUxNFx1YjI5NCBcdWM3NGNcdWM3NTggXHVjNWYwXHVjMThkXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjNzRjXHVjNzQwIFx1YzkwNFx1YzVkMFx1YzExYyBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM5MDRcdWM3NDQgXHVkMjk1XHVhZTMwXHViYTc0IFx1YzVmMFx1YzhmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCA0XHViYzg4IFx1YzkwNFx1Yzc1OCA4XHViYzg4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWIyMDRcdWI5NzRcdWFjZTAgXHVkMjk1XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1YzkwNFx1Yzc1OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWIyMDRcdWI5NzRcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWM3NGNcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAzXHViYzg4IFx1YzkwNFx1Yzc1OCA1XHViYzg4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWM3NzRcdWJiZjggXHViMjA0XHViOTc0XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YywgN1x1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWJhNzQsIDVcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWMxOTBcdWM3NDQgXHViNWJjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWIyZTRcdWI5NzggXHVjMTkwXHVhYzAwXHViNzdkXHVjNzNjXHViODVjIDdcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM5MDRcdWM3NDQgXHVkMjk1XHVhZTMwXHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzU4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0XHViYTc0LCA1XHViYzg4XHVhY2ZjIDdcdWJjODhcdWM3NDQgXHViMjA0XHViOTc0XHViMzU4IFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWI1YzAgXHViMmU0XHVjNzRjXHVjNWQwIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM1ZjBcdWM4ZmNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+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