시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB270826634.737%

문제

상근이는 점점 부자가 되었고 트럭 운송 회사를 차렸다. 이 회사에는 트럭이 총 N대 있고, 모든 배달은 "공부 고속도로"를 통해 이루어진다.

공부 고속도로에는 나들목(인터체인지, IC)이 1,000,000개 있다. 그리고, 각 나들목은 1번부터 순서대로 번호가 매겨져 있다. 나들목에서는 고속도로로 들어오거나 나갈 수 있다.

고속도로에 들어갈 때는 들어온 나들목의 번호가 적혀있는 티켓을 하나 받게 된다. 이 티켓은 고속도로에서 나갈 때 요금소(톨게이트)에 제시해야하고, 들어온 나들목과 나가는 나들목 번호의 차이만큼 요금을 내야 한다. 예를 들어, 티켓에 적혀있는 나들목의 번호가 30이고 12번 나들목으로 나간다면, 요금은 18원이 된다.

고속도로 이용 요금은 점점 회사가 감당할 수 없는 수준까지 치솟았고, 상근이는 획기적인 방법을 생각해냈다. 바로, 고속도로 중간에서 두 운전사가 만나서 티켓을 교환하는 것이다. 이 방법은 서로 경로가 겹치지 않더라도 교환할 수 있으며, 티켓은 여러 번 교환할 수 있다.

하지만, 의심을 피하기 위해서 티켓에 적혀있는 나들목의 번호와 같은 나들목으로 나갈 수는 없다. 

운전사끼리 티켓을 적절히 교환했을 때, 내야하는 고속도로 이용 요금의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 트럭의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 트럭이 들어온 나들목의 번호와 나가야 하는 나들목의 번호가 공백으로 구분해서 주어진다. 나들목의 번호는 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다.

두 트럭이 고속도로로 들어올 때 사용하는 나들목의 번호나 나갈 때 사용하는 나들목의 번호가 같은 경우는 없다.

출력

상근이네 트럭 운송 회사가 내야하는 고속도로 이용 요금의 최솟값을 출력한다. 이 값은 32비트 정수 범위를 넘어갈 수 있기 때문에, 64비트 정수(C/C++: long long)을 사용해야 한다.

예제 입력 1

3
3 65
45 10
60 25

예제 출력 1

32

예제 입력 2

3
5 5
6 7
8 8

예제 출력 2

5
W3sicHJvYmxlbV9pZCI6IjI5ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTBcdWM4MTAgXHViZDgwXHVjNzkwXHVhYzAwIFx1YjQxOFx1YzVjOFx1YWNlMCBcdWQyYjhcdWI3ZWQgXHVjNmI0XHVjMWExIFx1ZDY4Y1x1YzBhY1x1Yjk3YyBcdWNjMjhcdWI4MzhcdWIyZTQuIFx1Yzc3NCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWIyOTQgXHVkMmI4XHViN2VkXHVjNzc0IFx1Y2QxZCBOXHViMzAwIFx1Yzc4OFx1YWNlMCwgXHViYWE4XHViNGUwIFx1YmMzMFx1YjJlY1x1Yzc0MCAmcXVvdDtcdWFjZjVcdWJkODAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjJnF1b3Q7XHViOTdjIFx1ZDFiNVx1ZDU3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmNVx1YmQ4MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM1ZDBcdWIyOTQgXHViMDk4XHViNGU0XHViYWE5KFx1Yzc3OFx1ZDEzMFx1Y2NiNFx1Yzc3OFx1YzljMCwgSUMpXHVjNzc0IDEsMDAwLDAwMFx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVhYzAxIFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViNGU0XHViYWE5XHVjNWQwXHVjMTFjXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjNzBcdWIwOTggXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHViNTRjXHViMjk0IFx1YjRlNFx1YzViNFx1YzYyOCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWQyZjBcdWNmMTNcdWM3NDQgXHVkNTU4XHViMDk4IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWQyZjBcdWNmMTNcdWM3NDAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNWQwXHVjMTFjIFx1YjA5OFx1YWMwOCBcdWI1NGMgXHVjNjk0XHVhZTA4XHVjMThjKFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOClcdWM1ZDAgXHVjODFjXHVjMmRjXHVkNTc0XHVjNTdjXHVkNTU4XHVhY2UwLCBcdWI0ZTRcdWM1YjRcdWM2MjggXHViMDk4XHViNGU0XHViYWE5XHVhY2ZjIFx1YjA5OFx1YWMwMFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTkgXHViYzg4XHVkNjM4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjljY1x1ZDA3YyBcdWM2OTRcdWFlMDhcdWM3NDQgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkMmYwXHVjZjEzXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIDMwXHVjNzc0XHVhY2UwIDEyXHViYzg4IFx1YjA5OFx1YjRlNFx1YmFhOVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDRcdWIyZTRcdWJhNzQsIFx1YzY5NFx1YWUwOFx1Yzc0MCAxOFx1YzZkMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzQwIFx1YzgxMFx1YzgxMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVhYzEwXHViMmY5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjOTAwXHVhZTRjXHVjOWMwIFx1Y2U1OFx1YzE5Zlx1YzU1OFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDY4ZFx1YWUzMFx1YzgwMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LiBcdWJjMTRcdWI4NWMsIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM5MTFcdWFjMDRcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YzZiNFx1YzgwNFx1YzBhY1x1YWMwMCBcdWI5Y2NcdWIwOThcdWMxMWMgXHVkMmYwXHVjZjEzXHVjNzQ0IFx1YWQ1MFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMzU0XHViNzdjXHViM2M0IFx1YWQ1MFx1ZDY1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQyZjBcdWNmMTNcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWFkNTBcdWQ2NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NThcdWMyZWNcdWM3NDQgXHVkNTNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQyZjBcdWNmMTNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjA5OFx1YjRlNFx1YmFhOVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDggXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNmI0XHVjODA0XHVjMGFjXHViMDdjXHViOWFjIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVhZDUwXHVkNjU4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMmI4XHViN2VkXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQyYjhcdWI3ZWRcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI4IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHViMDk4XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVkMmI4XHViN2VkXHVjNzc0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MmMgXHViNTRjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHViMDk4IFx1YjA5OFx1YWMwOCBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1ZDJiOFx1YjdlZCBcdWM2YjRcdWMxYTEgXHVkNjhjXHVjMGFjXHVhYzAwIFx1YjBiNFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMgXHVjNzc0XHVjNmE5IFx1YzY5NFx1YWUwOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOCBcdWJjOTRcdWM3MDRcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCA2NFx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMTgoQ1wvQysrOiBsb25nIGxvbmcpXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNFU1RBUklORSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBzaW5nbGUgZGF5LCBOIG9mIEx1a2EmIzM5O3MgdHJ1Y2tzIHRyYXZlbCBhIHNwZWNpZmljIGhpZ2h3YXkuIFRoZSBoaWdod2F5IGhhcyBhIG51bWJlciBvZiBleGl0cyBhbmQgZW50cmFuY2VzLiBBbiBleGl0IHdpdGggYSBwYXJ0aWN1bGFyIG51bWJlciBpcyBpbiB0aGUgc2FtZSBsb2NhdGlvbiBhcyB0aGUgZW50cmFuY2Ugd2l0aCB0aGF0IG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VXBvbiBlbnRlcmluZyB0aGUgaGlnaHdheSwgYSB0cnVjayBkcml2ZXIgcmVjZWl2ZXMgYSB0aWNrZXQgd2hpY2ggaW5kaWNhdGVzIHRoZSBlbnRyYW5jZSBoZSB1c2VkLiBXaGVuIGV4aXRpbmcsIHRoZSBkcml2ZXIgcGF5cyBhIHRvbGwgZXF1YWwgdG8gdGhlIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgdGhlIGVudHJhbmNlIGFuZCBleGl0IG51bWJlcnMuIEZvciBleGFtcGxlLCBpZiBhIHRpY2tldCBzYXlzIGhlIHVzZWQgZW50cmFuY2UgMzAsIHRoZW4gZXhpdGluZyBhdCBleGl0IDEyIHdpbGwgY29zdCBoaW0gMTguJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EgaGFzIGZpZ3VyZWQgb3V0IGEgd2F5IHRvIHNhdmUgdG9sbCBtb25leSB0aGF0IGhpcyBjb21wYW55IGRhaWx5IHNwZW5kcy4gQW55IHR3byBkcml2ZXJzIGNhbiBtZWV0IG9uIHRoZSBoaWdod2F5IGFuZCBleGNoYW5nZSB0aWNrZXRzLCBldmVuIGlmIHRoZWlyIHJvdXRlcyBkb24mIzM5O3Qgb3ZlcmxhcC4gVGlja2V0cyBjYW4gYmUgZXhjaGFuZ2VkIGFuIGFyYml0cmFyeSBudW1iZXIgb2YgdGltZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIGEgZHJpdmVyIGNhbm5vdCB1c2UgYW4gZXhpdCBpZiBoaXMgdGlja2V0IHNheXMgaGUgdXNlZCB0aGUgc2FtZSBlbnRyYW5jZSwgc2luY2UgdGhhdCB3b3VsZCBiZSBzdXNwaWNpb3VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBsZWFzdCB0b3RhbCBhbW91bnQgb2YgdG9sbHMgdGhhdCB0aGUgZHJpdmVycyBjYW4gYWNoaWV2ZSBieSBleGNoYW5naW5nIHRpY2tldHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgdHJ1Y2tzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gZGlzdGluY3QgaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCAxMDAwMDAwLiBUaGVzZSBhcmUgaW4gb3JkZXIgdGhlIGVudHJhbmNlIGFuZCBleGl0IG51bWJlcnMgb2Ygb25lIHRydWNrLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gdHJ1Y2tzIHdpbGwgdXNlIHRoZSBzYW1lIGhpZ2h3YXkgZW50cmFuY2Ugb3IgdGhlIHNhbWUgZXhpdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxlYXN0IHRvdGFsIGFtb3VudCBvZiB0b2xscyBMdWthJiMzOTtzIGNvbXBhbnkgbXVzdCBwYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHVzZSA2NC1iaXQgaW50ZWdlciB0eXBlcyAobG9uZyBsb25nIGluIENcL0MrKywgaW50NjQgaW4gUGFzY2FsKS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUsIHRoZSBmaXJzdCBhbmQgdGhpcmQgZHJpdmVycyB3aWxsIGV4Y2hhbmdlIHRpY2tldHMuIEFmdGVyIHRoaXMsIHRoZSBzZWNvbmQgYW5kIHRoaXJkIGRyaXZlcnMgZXhjaGFuZ2UgdGlja2V0cy4gQWZ0ZXIgdGhpcywgdGhlIGRyaXZlcnMgd2lsbCBoYXZlIHRoZSB0aWNrZXRzIDYwLCAzLCA0NSwgcmVzcGVjdGl2ZWx5LiBUaGUgdG90YWwgYW1vdW50IGluIHRvbGxzIGlzIHw2NSZtaW51czs2MHwgKyB8MTAmbWludXM7M3wgKyB8MjUmbWludXM7NDV8ID0gMzIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 6번

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