시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 134 35 26 39.394%

문제

상근이는 점점 부자가 되었고 트럭 운송 회사를 차렸다. 이 회사에는 트럭이 총 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

힌트

W3sicHJvYmxlbV9pZCI6IjI5ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTBcdWM4MTAgXHViZDgwXHVjNzkwXHVhYzAwIFx1YjQxOFx1YzVjOFx1YWNlMCBcdWQyYjhcdWI3ZWQgXHVjNmI0XHVjMWExIFx1ZDY4Y1x1YzBhY1x1Yjk3YyBcdWNjMjhcdWI4MzhcdWIyZTQuIFx1Yzc3NCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWIyOTQgXHVkMmI4XHViN2VkXHVjNzc0IFx1Y2QxZCBOXHViMzAwIFx1Yzc4OFx1YWNlMCwgXHViYWE4XHViNGUwIFx1YmMzMFx1YjJlY1x1Yzc0MCAmcXVvdDtcdWFjZjVcdWJkODAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjJnF1b3Q7XHViOTdjIFx1ZDFiNVx1ZDU3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWNmNVx1YmQ4MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM1ZDBcdWIyOTQgXHViMDk4XHViNGU0XHViYWE5KFx1Yzc3OFx1ZDEzMFx1Y2NiNFx1Yzc3OFx1YzljMCwgSUMpXHVjNzc0IDEsMDAwLDAwMFx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVhYzAxIFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViNGU0XHViYWE5XHVjNWQwXHVjMTFjXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjNzBcdWIwOTggXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHViNTRjXHViMjk0IFx1YjRlNFx1YzViNFx1YzYyOCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWQyZjBcdWNmMTNcdWM3NDQgXHVkNTU4XHViMDk4IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWQyZjBcdWNmMTNcdWM3NDAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNWQwXHVjMTFjIFx1YjA5OFx1YWMwOCBcdWI1NGMgXHVjNjk0XHVhZTA4XHVjMThjKFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOClcdWM1ZDAgXHVjODFjXHVjMmRjXHVkNTc0XHVjNTdjXHVkNTU4XHVhY2UwLCBcdWI0ZTRcdWM1YjRcdWM2MjggXHViMDk4XHViNGU0XHViYWE5XHVhY2ZjIFx1YjA5OFx1YWMwMFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTkgXHViYzg4XHVkNjM4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjljY1x1ZDA3YyBcdWM2OTRcdWFlMDhcdWM3NDQgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkMmYwXHVjZjEzXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWIwOThcdWI0ZTRcdWJhYTlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIDMwXHVjNzc0XHVhY2UwIDEyXHViYzg4IFx1YjA5OFx1YjRlNFx1YmFhOVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDRcdWIyZTRcdWJhNzQsIFx1YzY5NFx1YWUwOFx1Yzc0MCAxOFx1YzZkMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzQwIFx1YzgxMFx1YzgxMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVhYzEwXHViMmY5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMjE4XHVjOTAwXHVhZTRjXHVjOWMwIFx1Y2U1OFx1YzE5Zlx1YzU1OFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDY4ZFx1YWUzMFx1YzgwMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LiBcdWJjMTRcdWI4NWMsIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM5MTFcdWFjMDRcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YzZiNFx1YzgwNFx1YzBhY1x1YWMwMCBcdWI5Y2NcdWIwOThcdWMxMWMgXHVkMmYwXHVjZjEzXHVjNzQ0IFx1YWQ1MFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMzU0XHViNzdjXHViM2M0IFx1YWQ1MFx1ZDY1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQyZjBcdWNmMTNcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWFkNTBcdWQ2NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NThcdWMyZWNcdWM3NDQgXHVkNTNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQyZjBcdWNmMTNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjA5OFx1YjRlNFx1YmFhOVx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDggXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNmI0XHVjODA0XHVjMGFjXHViMDdjXHViOWFjIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVhZDUwXHVkNjU4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG5cclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI3ZWRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDJiOFx1YjdlZFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjggXHViMDk4XHViNGU0XHViYWE5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWIwOThcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWQyYjhcdWI3ZWRcdWM3NzQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyYyBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjA5OFx1YjRlNFx1YmFhOVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIwOTggXHViMDk4XHVhYzA4IFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViMDk4XHViNGU0XHViYWE5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVkMmI4XHViN2VkIFx1YzZiNFx1YzFhMSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDY0XHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOChDXC9DKys6IGxvbmcgbG9uZylcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ0VTVEFSSU5FIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIHNpbmdsZSBkYXksIE4gb2YgTHVrYSYjMzk7cyB0cnVja3MgdHJhdmVsIGEgc3BlY2lmaWMgaGlnaHdheS4gVGhlIGhpZ2h3YXkgaGFzIGEgbnVtYmVyIG9mIGV4aXRzIGFuZCBlbnRyYW5jZXMuIEFuIGV4aXQgd2l0aCBhIHBhcnRpY3VsYXIgbnVtYmVyIGlzIGluIHRoZSBzYW1lIGxvY2F0aW9uIGFzIHRoZSBlbnRyYW5jZSB3aXRoIHRoYXQgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5VcG9uIGVudGVyaW5nIHRoZSBoaWdod2F5LCBhIHRydWNrIGRyaXZlciByZWNlaXZlcyBhIHRpY2tldCB3aGljaCBpbmRpY2F0ZXMgdGhlIGVudHJhbmNlIGhlIHVzZWQuIFdoZW4gZXhpdGluZywgdGhlIGRyaXZlciBwYXlzIGEgdG9sbCBlcXVhbCB0byB0aGUgYWJzb2x1dGUgZGlmZmVyZW5jZSBvZiB0aGUgZW50cmFuY2UgYW5kIGV4aXQgbnVtYmVycy4gRm9yIGV4YW1wbGUsIGlmIGEgdGlja2V0IHNheXMgaGUgdXNlZCBlbnRyYW5jZSAzMCwgdGhlbiBleGl0aW5nIGF0IGV4aXQgMTIgd2lsbCBjb3N0IGhpbSAxOC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBoYXMgZmlndXJlZCBvdXQgYSB3YXkgdG8gc2F2ZSB0b2xsIG1vbmV5IHRoYXQgaGlzIGNvbXBhbnkgZGFpbHkgc3BlbmRzLiBBbnkgdHdvIGRyaXZlcnMgY2FuIG1lZXQgb24gdGhlIGhpZ2h3YXkgYW5kIGV4Y2hhbmdlIHRpY2tldHMsIGV2ZW4gaWYgdGhlaXIgcm91dGVzIGRvbiYjMzk7dCBvdmVybGFwLiBUaWNrZXRzIGNhbiBiZSBleGNoYW5nZWQgYW4gYXJiaXRyYXJ5IG51bWJlciBvZiB0aW1lcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgYSBkcml2ZXIgY2Fubm90IHVzZSBhbiBleGl0IGlmIGhpcyB0aWNrZXQgc2F5cyBoZSB1c2VkIHRoZSBzYW1lIGVudHJhbmNlLCBzaW5jZSB0aGF0IHdvdWxkIGJlIHN1c3BpY2lvdXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIGxlYXN0IHRvdGFsIGFtb3VudCBvZiB0b2xscyB0aGF0IHRoZSBkcml2ZXJzIGNhbiBhY2hpZXZlIGJ5IGV4Y2hhbmdpbmcgdGlja2V0cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiB0cnVja3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBkaXN0aW5jdCBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIDEwMDAwMDAuIFRoZXNlIGFyZSBpbiBvcmRlciB0aGUgZW50cmFuY2UgYW5kIGV4aXQgbnVtYmVycyBvZiBvbmUgdHJ1Y2suJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vIHR3byB0cnVja3Mgd2lsbCB1c2UgdGhlIHNhbWUgaGlnaHdheSBlbnRyYW5jZSBvciB0aGUgc2FtZSBleGl0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGVhc3QgdG90YWwgYW1vdW50IG9mIHRvbGxzIEx1a2EmIzM5O3MgY29tcGFueSBtdXN0IHBheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdXNlIDY0LWJpdCBpbnRlZ2VyIHR5cGVzIChsb25nIGxvbmcgaW4gQ1wvQysrLCBpbnQ2NCBpbiBQYXNjYWwpLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==