시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 297 160 134 60.090%

문제

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 <= N <= 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

입력

첫 번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x 좌표, 두 번째 정수는 y 좌표이다.

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

출력

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

예제 입력 1

4
0 0
8 3
11 -1
10 0

예제 출력 1

14

힌트

젖소 박승원은 2번째 혹은 3번째 체크포인트를 건너뛸 수 있는데, 여기서 두 번째 체크포인트를 건너뛸 경우 경로는 (0,0) -> (11,-1) -> (10,0) 이 되며 거리는 14이다. 박승원은 이것보다 더 짧게 달릴 수 없다.

W3sicHJvYmxlbV9pZCI6IjEwNjU1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWM4XHViNzdjXHVkMWE0IDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YzdhNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE2XHVjMThjXHViNGU0XHVjNzc0IFx1YWM3NFx1YWMxNVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHVjODE2XHVjMThjXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU1YyBcdWI5YzhcdWI3N2NcdWQxYTQgXHViMzAwXHVkNjhjXHViOTdjIFx1YzVmNFx1YzVjOFx1YWNlMCwgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc1OCBcdWNkMWRcdWM1NjBcdWI5N2MgXHViYzFiXHViMjk0IFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDAgXHVjNWVkXHVjMmRjIFx1Yzc3NCBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTYwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHViNzdjXHVkMWE0IFx1Y2Y1NFx1YzJhNFx1YjI5NCBOICgzICZsdDs9IE4gJmx0Oz0gMTAwMDAwKSBcdWFjMWNcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIDFcdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjY2I0XHVkMDZjIFx1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzI5XHViYjM4XHVkNTVjIFx1ZDZjNCBOXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2NcdWM5YzAgXHViOWM4XHViNzdjXHVkMWE0XHVjNzc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVhYzhjXHVjNzNjXHViOTc4IFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NDAgXHViOWM5XHVjMGMxIFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWI4MjQgXHVkNTU4XHViMmM4IFx1YWRjMFx1Y2MyZVx1YzU0NFx1YzgzOFx1YzExYyBcdWM5MTFcdWFjMDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOCBcdWQ1NWNcdWFjMWNcdWI5N2MgXHViYWIwXHViNzk4IFx1YWM3NFx1YjEwOFx1YjZmMFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgMVx1YmM4OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM2NDAgTlx1YmM4OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmYwXHViYTc0IFx1YjEwOFx1YmIzNCBcdWIyMDhcdWNlNThcdWFjMDAgXHViY2Y0XHVjNzc0XHViMmM4IFx1YjQ1MCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWIyOTQgXHVhYzc0XHViMTA4XHViNmYwXHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMwZGRcdWFjMDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NzQgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4IFx1ZDU1Y1x1YWMxY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWJhNzRcdWMxMWMgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWNmY1x1YzVmMCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHViMmVjXHViODI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVhYzcwXHViOWFjXHViMjk0IFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG5cclxuPHA+XHVjYzM4XHVhY2UwXHViODVjLCBcdWM4MTZcdWMxOGMgXHViOWM4XHViNzdjXHVkMWE0IFx1YjMwMFx1ZDY4Y1x1YjI5NCBcdWMxMWNcdWM2YjhcdWMyZGNcdWIwYjQgXHVkNTVjXHViY2Y1XHVkMzEwXHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1YjQyMCBcdWM2MDhcdWM4MTVcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM3MFx1YjlhY1x1YjI5NCBcdWQwZGRcdWMyZGMgXHVhYzcwXHViOWFjKE1hbmhhdHRhbiBEaXN0YW5jZSlcdWI4NWMgXHVhY2M0XHVjMGIwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCAoeDEseTEpXHVhY2ZjICh4Mix5MikgXHVjODEwIFx1YWMwNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgfHgxLXgyfCArIHx5MS15MnwgXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAofHh8XHViMjk0IFx1YzgwOFx1YjMxM1x1YWMxMiBcdWFlMzBcdWQ2MzhcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWI0NTBcdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggaVx1Yzc1OCB4IFx1Yzg4Y1x1ZDQ1YywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgeSBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1ZDA2YyBcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0IC0gXHVjODE2XHVjMThjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc0MCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4IFx1YjU0YyBcdWFkZjggXHViYzg4XHVkNjM4XHVjNzU4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YjljYyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWJhNzAsIFx1YWRmOCBcdWM4MTBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHVjODE2XHVjMThjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc3NCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggMVx1YWMxY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWFjZTAgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NDAgMlx1YmM4OFx1YzlmOCBcdWQ2MzlcdWM3NDAgM1x1YmM4OFx1YzlmOCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YzVlY1x1YWUzMFx1YzExYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWFjNzRcdWIxMDhcdWI2ZjggXHVhY2JkXHVjNmIwIFx1YWNiZFx1Yjg1Y1x1YjI5NCAoMCwwKSAtJmd0OyAoMTEsLTEpIC0mZ3Q7ICgxMCwwKSBcdWM3NzQgXHViNDE4XHViYTcwIFx1YWM3MFx1YjlhY1x1YjI5NCAxNFx1Yzc3NFx1YjJlNC4gXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1Yzc3NFx1YWM4M1x1YmNmNFx1YjJlNCBcdWIzNTQgXHVjOWU3XHVhYzhjIFx1YjJlY1x1YjliNCBcdWMyMTggXHVjNWM2XHViMmU0LlxyXG48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNjU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFyYXRob24iLCJkZXNjcmlwdGlvbiI6IjxwPlVuaGFwcHkgd2l0aCB0aGUgcG9vciBoZWFsdGggb2YgaGlzIGNvd3MsIEZhcm1lciBKb2huIGVucm9sbHMgdGhlbSBpbiBhbiBhc3NvcnRtZW50IG9mIGRpZmZlcmVudCBwaHlzaWNhbCBmaXRuZXNzIGFjdGl2aXRpZXMuICZuYnNwO0hpcyBwcml6ZSBjb3cgQmVzc2llIGlzIGVucm9sbGVkIGluIGEgcnVubmluZyBjbGFzcywgd2hlcmUgc2hlIGlzIGV2ZW50dWFsbHkgZXhwZWN0ZWQgdG8gcnVuIGEgbWFyYXRob24gdGhyb3VnaCB0aGUgZG93bnRvd24gYXJlYSBvZiB0aGUgY2l0eSBuZWFyIEZhcm1lciBKb2huJiMzOTtzIGZhcm0hPFwvcD5cclxuXHJcbjxwPlRoZSBtYXJhdGhvbiBjb3Vyc2UgY29uc2lzdHMgb2YgTiBjaGVja3BvaW50cyAoMyAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIHRvIGJlIHZpc2l0ZWQgaW4gc2VxdWVuY2UsIHdoZXJlIGNoZWNrcG9pbnQgMSBpcyB0aGUgc3RhcnRpbmcgbG9jYXRpb24gYW5kIGNoZWNrcG9pbnQgTiBpcyB0aGUgZmluaXNoLiAmbmJzcDtCZXNzaWUgaXMgc3VwcG9zZWQgdG8gdmlzaXQgYWxsIG9mIHRoZXNlIGNoZWNrcG9pbnRzIG9uZSBieSBvbmUsIGJ1dCBiZWluZyB0aGUgbGF6eSBjb3cgc2hlIGlzLCBzaGUgZGVjaWRlcyB0aGF0IHNoZSB3aWxsIHNraXAgdXAgdG8gb25lIGNoZWNrcG9pbnQgaW4gb3JkZXIgdG8gc2hvcnRlbiBoZXIgdG90YWwgam91cm5leS4gJm5ic3A7U2hlIGNhbm5vdCBza2lwIGNoZWNrcG9pbnRzIDEgb3IgTiwgaG93ZXZlciwgc2luY2UgdGhhdCB3b3VsZCBiZSB0b28gbm90aWNlYWJsZS48XC9wPlxyXG5cclxuPHA+UGxlYXNlIGhlbHAgQmVzc2llIGZpbmQgdGhlIG1pbmltdW0gZGlzdGFuY2UgdGhhdCBzaGUgaGFzIHRvIHJ1biBpZiBzaGUgY2FuIHNraXAgdXAgdG8gb25lIGNoZWNrcG9pbnQuICZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgc2luY2UgdGhlIGNvdXJzZSBpcyBzZXQgaW4gYSBkb3dudG93biBhcmVhIHdpdGggYSBncmlkIG9mIHN0cmVldHMsIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBjaGVja3BvaW50cyBhdCBsb2NhdGlvbnMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGlzIGdpdmVuIGJ5IHx4MS14MnwgKyB8eTEteTJ8LiAmbmJzcDtUaGlzIHdheSBvZiBtZWFzdXJpbmcgZGlzdGFuY2UgLS0gYnkgdGhlIGRpZmZlcmVuY2UgaW4geCBwbHVzIHRoZSBkaWZmZXJlbmNlIGluIHkgLS0gaXMgc29tZXRpbWVzIGtub3duIGFzICZxdW90O01hbmhhdHRhbiZxdW90OyBkaXN0YW5jZSBiZWNhdXNlIGl0IHJlZmxlY3RzIHRoZSBmYWN0IHRoYXQgaW4gYSBkb3dudG93biBncmlkLCB5b3UgY2FuIHRyYXZlbCBwYXJhbGxlbCB0byB0aGUgeCBvciB5IGF4ZXMsIGJ1dCB5b3UgY2Fubm90IHRyYXZlbCBhbG9uZyBhIGRpcmVjdCBsaW5lICZxdW90O2FzIHRoZSBjcm93IGZsaWVzJnF1b3Q7LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgZ2l2ZXMgdGhlIHZhbHVlIG9mIE4uPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgZWFjaCBjb250YWluIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHggYW5kIHksIHJlcHJlc2VudGluZyBhIGNoZWNrcG9pbnQgKC0xMDAwICZsdDs9IHggJmx0Oz0gMTAwMCwgLTEwMDAgJmx0Oz0geSAmbHQ7PSAxMDAwKS4gVGhlIGNoZWNrcG9pbnRzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgdGhhdCB0aGV5IG11c3QgYmUgdmlzaXRlZC4gTm90ZSB0aGF0IHRoZSBjb3Vyc2UgbWlnaHQgY3Jvc3Mgb3ZlciBpdHNlbGYgc2V2ZXJhbCB0aW1lcywgd2l0aCBzZXZlcmFsIGNoZWNrcG9pbnRzIG9jY3VycmluZyBhdCB0aGUgc2FtZSBwaHlzaWNhbCBsb2NhdGlvbi4gJm5ic3A7V2hlbiBCZXNzaWUgc2tpcHMgc3VjaCBhIGNoZWNrcG9pbnQsIHNoZSBvbmx5IHNraXBzIG9uZSBpbnN0YW5jZSBvZiB0aGUgY2hlY2twb2ludCAtLSBzaGUgZG9lcyBub3Qgc2tpcCBldmVyeSBjaGVja3BvaW50IG9jY3VycmluZyBhdCB0aGUgc2FtZSBsb2NhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gZGlzdGFuY2UgdGhhdCBCZXNzaWUgY2FuIHJ1biBieSBza2lwcGluZyB1cCB0byBvbmUgY2hlY2twb2ludC4gJm5ic3A7RG9uJiMzOTt0IGZvcmdldCB0byBlbmQgeW91ciBvdXRwdXQgd2l0aCBhIG5ld2xpbmUuICZuYnNwO0luIHRoZSBzYW1wbGUgY2FzZSBzaG93biBoZXJlLCBza2lwcGluZyB0aGUgY2hlY2twb2ludCBhdCAoOCwgMykgbGVhZHMgdG8gdGhlIG1pbmltdW0gdG90YWwgZGlzdGFuY2Ugb2YgMTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d