시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB108485247400347.050%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

7

예제 입력 2

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

예제 출력 2

9
W3sicHJvYmxlbV9pZCI6IjI4NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NTggXHVhZTMwXHVkMGMwIFx1YzVmMFx1YzhmYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzBjMVx1YzBjMVx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzQwIFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWMyMThcdWMyZWRcdWM1YjVcdWFjMWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NDAgXHVhZTMwXHVkMGMwXHVhYzAwIFx1Y2U1OFx1YWNlMCBcdWMyZjZcdWM1YzhcdWFjZTAsIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzVkMFx1YzExYyBcdWFjMDRcdWIyZThcdWQ1NWMgXHViYTVjXHViODVjXHViNTE0XHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU4OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1Yzc3NCBcdWFlMzBcdWQwYzBcdWI5N2MgXHVjZTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2Y0XHVkMWI1IFx1YWUzMFx1ZDBjMFx1YjI5NCAxXHViYzg4IFx1YzkwNFx1YmQ4MFx1ZDEzMCA2XHViYzg4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWNkMWQgNlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIFBcdWFjMWNcdWM3NTggXHVkNTA0XHViODFiXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIzYzQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBQXHViYzg4XHVhZTRjXHVjOWMwIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE1Y1x1Yjg1Y1x1YjUxNFx1YjI5NCBcdWM3NGNcdWM3NTggXHVjNWYwXHVjMThkXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjNzRjXHVjNzQwIFx1YzkwNFx1YzVkMFx1YzExYyBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM5MDRcdWM3NDQgXHVkMjk1XHVhZTMwXHViYTc0IFx1YzVmMFx1YzhmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCA0XHViYzg4IFx1YzkwNFx1Yzc1OCA4XHViYzg4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWIyMDRcdWI5NzRcdWFjZTAgXHVkMjk1XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1YzkwNFx1Yzc1OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWIyMDRcdWI5NzRcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWM3NGNcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAzXHViYzg4IFx1YzkwNFx1Yzc1OCA1XHViYzg4IFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWM3NzRcdWJiZjggXHViMjA0XHViOTc0XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YywgN1x1YmM4OCBcdWQ1MDRcdWI4MWJcdWM3NDQgXHViMjA0XHViOTc4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWJhNzQsIDVcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWMxOTBcdWM3NDQgXHViNWJjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWIyZTRcdWI5NzggXHVjMTkwXHVhYzAwXHViNzdkXHVjNzNjXHViODVjIDdcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM5MDRcdWM3NDQgXHVkMjk1XHVhZTMwXHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzU4IFx1Yzc0Y1x1Yzc0NCBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0XHViYTc0LCA1XHViYzg4XHVhY2ZjIDdcdWJjODhcdWM3NDQgXHViMjA0XHViOTc0XHViMzU4IFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWI1YzAgXHViMmU0XHVjNzRjXHVjNWQwIDJcdWJjODggXHVkNTA0XHViODFiXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YWNlMCBcdWM1ZjBcdWM4ZmNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjMTkwXHVhYzAwXHViNzdkXHVjNzNjXHViODVjIFx1ZDUwNFx1YjgxYlx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YjIwNFx1Yjk3NFx1YWM3MFx1YjA5OCBcdWI1YmNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1YzYwMFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWJhNWNcdWI4NWNcdWI1MTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTkwXHVhYzAwXHViNzdkXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYTVjXHViODVjXHViNTE0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjNzRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwMCwwMDAsIDIgJmxlOyBQICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmE1Y1x1Yjg1Y1x1YjUxNFx1Yzc1OCBcdWQ1NWMgXHVjNzRjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjOTA0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFkZjggXHVjOTA0XHVjNWQwXHVjMTFjIFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODFiXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3NGNcdWM3NTggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWUzMFx1ZDBjMFx1Yjk3YyBcdWM1ZjBcdWM4ZmNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5MDRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIFx1ZDUwNFx1YjgxYlx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIzYzQgUFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1Y1x1Yjg1Y1x1YjUxNFx1Yjk3YyBcdWM1ZjBcdWM4ZmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMxOTBcdWFjMDBcdWI3N2QgXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0lUQVJBIiwiZGVzY3JpcHRpb24iOiI8cD5EYXJrbyBoYXMgYSBuZXcgaW1hZ2luYXJ5IGV4dHJhdGVycmVzdHJpYWwgZnJpZW5kIHdpdGggYSBiaWxsaW9uIG9mIGZpbmdlcnMuIFRoZSBleHRyYXRlcnJlc3RyaWFsIGhhcyBzb29uIHRvb2sgaG9sZCBvZiBoaXMgZ3VpdGFyLCBmb3VuZCBhIHNpbXBsZSBtZWxvZHkgb25saW5lLCBhbmQgc3RhcnRlZCBwbGF5aW5nIGl0LjxcL3A+XHJcblxyXG48cD5UaGUgZ3VpdGFyLCBhcyB1c3VhbCwgaGFzIHNpeCBzdHJpbmdzIGRlbm90ZWQgYnkgbnVtYmVycyAxIHRocm91Z2ggNi4gRWFjaCBzdHJpbmcgaXMgZGl2aWRlZCBpbnRvIFAgZnJldHMgZGVub3RlZCBieSBudW1iZXJzIDEgdGhyb3VnaCBQLjxcL3A+XHJcblxyXG48cD5BIG1lbG9keSBpcyBhIHNlcXVlbmNlIG9mIHRvbmVzLCB3aGVyZSBlYWNoIHRvbmUgaXMgcHJvZHVjZWQgYnkgcGlja2luZyBhIHN0cmluZyBwcmVzc2VkIG9uIGEgc3BlY2lmaWMgZnJldCAoZS5nLiA0dGggc3RyaW5nIHByZXNzZWQgb24gdGhlIDh0aCBmcmV0KS4gSWYgYSBzdHJpbmcgaXMgcHJlc3NlZCBvbiBzZXZlcmFsIGZyZXRzLCB0aGUgcHJvZHVjZWQgdG9uZSB3aWxsIGJlIHRoZSBvbmUgY29ycmVzcG9uZGluZyB0byB0aGUgaGlnaGVzdCBvZiB0aG9zZSBmcmV0cy48XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBpZiB0aGUgM3JkIHN0cmluZyBpcyBhbHJlYWR5IHByZXNzZWQgb24gdGhlIDV0aCBmcmV0LCBhbmQgdGhlIHRvbmUgd2hpY2ggY29ycmVzcG9uZHMgdG8gdGhlIDd0aCBmcmV0IGlzIHRvIGJlIHByb2R1Y2VkLCB0aGUgc3RyaW5nIGNhbiBiZSBwcmVzc2VkIG9uIHRoZSA3dGggZnJldCBhbmQgcGlja2VkIHdpdGhvdXQgcmVsZWFzaW5nIHRoZSA1dGggZnJldCwgc2luY2Ugb25seSB0aGUgaGlnaGVzdCBvbmUgYWZmZWN0cyB0aGUgdG9uZSBwcm9kdWNlZCAoN3RoIGluIHRoaXMgY2FzZSkuIFNpbWlsYXJseSwgaWYgYSB0b25lIHRoYXQgY29ycmVzcG9uZHMgdG8gdGhlIDJuZCBmcmV0IG9uIHRoZSBzYW1lIHN0cmluZyBpcyBuZXh0IHRvIGJlIHByb2R1Y2VkLCBpdCBpcyBuZWNlc3NhcnkgdG8gcmVsZWFzZSBib3RoIDV0aCBhbmQgN3RoIGZyZXRzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggY29tcHV0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZpbmdlciBtb3ZlbWVudHMgbmVlZGVkIHRvIHByb2R1Y2UgdGhlIGdpdmVuIG1lbG9keS4gTm90ZSB0aGF0IHByZXNzIG9yIHJlbGVhc2UgYSBzaW5nbGUgZnJldCBjb3VudHMgYXMgb25lIGZpbmdlciBtb3ZlLiBTdHJpbmcgcGlja2luZyBkb2VzIG5vdCBjb3VudCBhcyBmaW5nZXIgbW92ZSwgYnV0IHJhdGhlciBhIGd1aXRhciBwaWNrIG1vdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCBOIChOICZsZTsgNTAwIDAwMCkgYW5kIFAgKDIgJmxlOyBQICZsZTsgMzAwIDAwMCkuIFRoZXkgcmVwcmVzZW50IHRoZSBudW1iZXIgb2YgdG9uZXMgaW4gdGhlIG1lbG9keSBhbmQgdGhlIG51bWJlciBvZiBmcmV0cywgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgZGVzY3JpYmUgdGhlIGZpZWxkcyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgdG9uZXMgJm5kYXNoOyB0aGUgb3JkaW5hbCBvZiB0aGUgc3RyaW5nIGFuZCB0aGUgb3JkaW5hbCBvZiB0aGUgZnJldCwgcmVzcGVjdGl2ZWx5LCBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgZXh0cmF0ZXJyZXN0cmlhbCBwbGF5IHRoZW0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQsIHByaW50IHRoZSBtaW5pbXVtIG51bWJlciBvZiBmaW5nZXIgbW92ZW1lbnRzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5GaXJzdCBzYW1wbGUgZGVzY3JpcHRpb246IGFsbCB0aGUgdG9uZXMgcGxheWVkIGFyZSBwcm9kdWNlZCBieSBwaWNraW5nIHRoZSAybmQgc3RyaW5nLiBGaXJzdCwgdGhlIGZyZXRzIDgsIDEwLCAxMiBhcmUgcHJlc3NlZCwgaW4gb3JkZXIgKHRocmVlIG1vdmVtZW50cykuIFRoZW4sIHRoZSAxMnRoIGZyZXQgaXMgcmVsZWFzZWQgdG8gcHJvZHVjZSB0aGUgc2Vjb25kIHRvbmUgYWdhaW4gKGZvdXJ0aCBtb3ZlbWVudCkuIEZpbmFsbHksIHRoZSA1dGggZnJldCBpcyBwcmVzc2VkIGZvbGxvd2VkIGJ5IHRoZSByZWxlYXNlIG9mIGZyZXRzIDEwIGFuZCAxMiAoYSB0b3RhbCBvZiBzZXZlbiBtb3ZlbWVudHMpLjxcL3A+XHJcblxyXG48cD5TZWNvbmQgc2FtcGxlIGRlc2NyaXB0aW9uOiAxLCAxLCAxLCAxLCAzLCAwLCAyIGZpbmdlciBtb3ZlbWVudHMgYXJlIG5lY2Vzc2FyeSwgaW4gdGhlIG9yZGVyIG9mIHRoZSBzZXZlbiB0b25lcyBwcm9kdWNlZC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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