시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2289 905 717 39.855%

문제

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

보통 기타는 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+XHViYTVjXHViODVjXHViNTE0XHViMjk0IFx1Yzc0Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWM3NGNcdWM3NDAgXHVjOTA0XHVjNWQwXHVjMTFjIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc0XHVhY2UwIFx1YzkwNFx1Yzc0NCBcdWQyOTVcdWFlMzBcdWJhNzQgXHVjNWYwXHVjOGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDRcdWJjODggXHVjOTA0XHVjNzU4IDhcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWQyOTVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM1YjRcdWI1YTQgXHVjOTA0XHVjNzU4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVkNTA0XHViODFiXHVjNzU4IFx1Yzc0Y1x1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDNcdWJjODggXHVjOTA0XHVjNzU4IDVcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1Yzc3NFx1YmJmOCBcdWIyMDRcdWI5NzRcdWFjZTAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCA3XHViYzg4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWIyMDRcdWI5NzggXHVjNzRjXHVjNzQ0IFx1YzVmMFx1YzhmY1x1ZDU1OFx1YjgyNFx1YmE3NCwgNVx1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc0XHViMjk0IFx1YzE5MFx1Yzc0NCBcdWI1YmNcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YjJlNFx1Yjk3OCBcdWMxOTBcdWFjMDBcdWI3N2RcdWM3M2NcdWI4NWMgN1x1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc0XHVhY2UwIFx1YzkwNFx1Yzc0NCBcdWQyOTVcdWFlMzBcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgMlx1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NTggXHVjNzRjXHVjNzQ0IFx1YzVmMFx1YzhmY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQsIDVcdWJjODhcdWFjZmMgN1x1YmM4OFx1Yzc0NCBcdWIyMDRcdWI5NzRcdWIzNTggXHVjMTkwXHVhYzAwXHViNzdkXHVjNzQ0IFx1YjVjMCBcdWIyZTRcdWM3NGNcdWM1ZDAgMlx1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc0XHVhY2UwIFx1YzVmMFx1YzhmY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMxOTBcdWFjMDBcdWI3N2RcdWM3M2NcdWI4NWMgXHVkNTA0XHViODFiXHVjNzQ0IFx1ZDU1YyBcdWJjODggXHViMjA0XHViOTc0XHVhYzcwXHViMDk4IFx1YjViY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjMTkwXHVhYzAwXHViNzdkXHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNjAwXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1YmE1Y1x1Yjg1Y1x1YjUxNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxOTBcdWFjMDBcdWI3N2RcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVkNjhjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhNWNcdWI4NWNcdWI1MTRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTA0XHViODFiXHVjNzU4IFx1YzIxOCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gJmxlOyA1MDAsMDAwLCAyICZsZTsgUCAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhNWNcdWI4NWNcdWI1MTRcdWM3NTggXHVkNTVjIFx1Yzc0Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IFx1YzkwNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhZGY4IFx1YzkwNFx1YzVkMFx1YzExYyBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzRjXHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFlMzBcdWQwYzBcdWI5N2MgXHVjNWYwXHVjOGZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1Y1x1Yjg1Y1x1YjUxNFx1Yjk3YyBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMxOTBcdWFjMDBcdWI3N2QgXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0lUQVJBIiwiZGVzY3JpcHRpb24iOiI8cD5EYXJrbyBoYXMgYSBuZXcgaW1hZ2luYXJ5IGV4dHJhdGVycmVzdHJpYWwgZnJpZW5kIHdpdGggYSBiaWxsaW9uIG9mIGZpbmdlcnMuIFRoZSBleHRyYXRlcnJlc3RyaWFsIGhhcyBzb29uIHRvb2sgaG9sZCBvZiBoaXMgZ3VpdGFyLCBmb3VuZCBhIHNpbXBsZSBtZWxvZHkgb25saW5lLCBhbmQgc3RhcnRlZCBwbGF5aW5nIGl0LjxcL3A+XHJcblxyXG48cD5UaGUgZ3VpdGFyLCBhcyB1c3VhbCwgaGFzIHNpeCBzdHJpbmdzIGRlbm90ZWQgYnkgbnVtYmVycyAxIHRocm91Z2ggNi4gRWFjaCBzdHJpbmcgaXMgZGl2aWRlZCBpbnRvIFAgZnJldHMgZGVub3RlZCBieSBudW1iZXJzIDEgdGhyb3VnaCBQLjxcL3A+XHJcblxyXG48cD5BIG1lbG9keSBpcyBhIHNlcXVlbmNlIG9mIHRvbmVzLCB3aGVyZSBlYWNoIHRvbmUgaXMgcHJvZHVjZWQgYnkgcGlja2luZyBhIHN0cmluZyBwcmVzc2VkIG9uIGEgc3BlY2lmaWMgZnJldCAoZS5nLiA0dGggc3RyaW5nIHByZXNzZWQgb24gdGhlIDh0aCBmcmV0KS4gSWYgYSBzdHJpbmcgaXMgcHJlc3NlZCBvbiBzZXZlcmFsIGZyZXRzLCB0aGUgcHJvZHVjZWQgdG9uZSB3aWxsIGJlIHRoZSBvbmUgY29ycmVzcG9uZGluZyB0byB0aGUgaGlnaGVzdCBvZiB0aG9zZSBmcmV0cy48XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBpZiB0aGUgM3JkIHN0cmluZyBpcyBhbHJlYWR5IHByZXNzZWQgb24gdGhlIDV0aCBmcmV0LCBhbmQgdGhlIHRvbmUgd2hpY2ggY29ycmVzcG9uZHMgdG8gdGhlIDd0aCBmcmV0IGlzIHRvIGJlIHByb2R1Y2VkLCB0aGUgc3RyaW5nIGNhbiBiZSBwcmVzc2VkIG9uIHRoZSA3dGggZnJldCBhbmQgcGlja2VkIHdpdGhvdXQgcmVsZWFzaW5nIHRoZSA1dGggZnJldCwgc2luY2Ugb25seSB0aGUgaGlnaGVzdCBvbmUgYWZmZWN0cyB0aGUgdG9uZSBwcm9kdWNlZCAoN3RoIGluIHRoaXMgY2FzZSkuIFNpbWlsYXJseSwgaWYgYSB0b25lIHRoYXQgY29ycmVzcG9uZHMgdG8gdGhlIDJuZCBmcmV0IG9uIHRoZSBzYW1lIHN0cmluZyBpcyBuZXh0IHRvIGJlIHByb2R1Y2VkLCBpdCBpcyBuZWNlc3NhcnkgdG8gcmVsZWFzZSBib3RoIDV0aCBhbmQgN3RoIGZyZXRzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggY29tcHV0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZpbmdlciBtb3ZlbWVudHMgbmVlZGVkIHRvIHByb2R1Y2UgdGhlIGdpdmVuIG1lbG9keS4gTm90ZSB0aGF0IHByZXNzIG9yIHJlbGVhc2UgYSBzaW5nbGUgZnJldCBjb3VudHMgYXMgb25lIGZpbmdlciBtb3ZlLiBTdHJpbmcgcGlja2luZyBkb2VzIG5vdCBjb3VudCBhcyBmaW5nZXIgbW92ZSwgYnV0IHJhdGhlciBhIGd1aXRhciBwaWNrIG1vdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCBOIChOICZsZTsgNTAwIDAwMCkgYW5kIFAgKDIgJmxlOyBQICZsZTsgMzAwIDAwMCkuIFRoZXkgcmVwcmVzZW50IHRoZSBudW1iZXIgb2YgdG9uZXMgaW4gdGhlIG1lbG9keSBhbmQgdGhlIG51bWJlciBvZiBmcmV0cywgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgZGVzY3JpYmUgdGhlIGZpZWxkcyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgdG9uZXMgJm5kYXNoOyB0aGUgb3JkaW5hbCBvZiB0aGUgc3RyaW5nIGFuZCB0aGUgb3JkaW5hbCBvZiB0aGUgZnJldCwgcmVzcGVjdGl2ZWx5LCBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgZXh0cmF0ZXJyZXN0cmlhbCBwbGF5IHRoZW0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQsIHByaW50IHRoZSBtaW5pbXVtIG51bWJlciBvZiBmaW5nZXIgbW92ZW1lbnRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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