시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 228 117 103 59.195%

문제

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

마라톤 코스는 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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQ1MFx1YWMxY1x1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4IGlcdWM3NTggeCBcdWM4OGNcdWQ0NWMsIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgeSBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1ZDA2YyBcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0IC0gXHVjODE2XHVjMThjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc0MCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4IFx1YjU0YyBcdWFkZjggXHViYzg4XHVkNjM4XHVjNzU4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YjljYyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWJhNzAsIFx1YWRmOCBcdWM4MTBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHVjODE2XHVjMThjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc3NCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggMVx1YWMxY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWFjZTAgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NDAgMlx1YmM4OFx1YzlmOCBcdWQ2MzlcdWM3NDAgM1x1YmM4OFx1YzlmOCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YzVlY1x1YWUzMFx1YzExYyBcdWI0NTBcdWJjODhcdWM5ZjggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1YWM3NFx1YjEwOFx1YjZmOCBcdWFjYmRcdWM2YjAgXHVhY2JkXHViODVjXHViMjk0ICgwLDApIC0mZ3Q7ICgxMSwtMSkgLSZndDsgKDEwLDApIFx1Yzc3NCBcdWI0MThcdWJhNzAgXHVhYzcwXHViOWFjXHViMjk0IDE0XHVjNzc0XHViMmU0LiBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NDAgXHVjNzc0XHVhYzgzXHViY2Y0XHViMmU0IFx1YjM1NCBcdWM5ZTdcdWFjOGMgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM1YzZcdWIyZTQuXHJcbjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA2NTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXJhdGhvbiIsImRlc2NyaXB0aW9uIjoiPHA+VW5oYXBweSB3aXRoIHRoZSBwb29yIGhlYWx0aCBvZiBoaXMgY293cywgRmFybWVyIEpvaG4gZW5yb2xscyB0aGVtIGluIGFuIGFzc29ydG1lbnQgb2YgZGlmZmVyZW50IHBoeXNpY2FsIGZpdG5lc3MgYWN0aXZpdGllcy4gJm5ic3A7SGlzIHByaXplIGNvdyBCZXNzaWUgaXMgZW5yb2xsZWQgaW4gYSBydW5uaW5nIGNsYXNzLCB3aGVyZSBzaGUgaXMgZXZlbnR1YWxseSBleHBlY3RlZCB0byBydW4gYSBtYXJhdGhvbiB0aHJvdWdoIHRoZSBkb3dudG93biBhcmVhIG9mIHRoZSBjaXR5IG5lYXIgRmFybWVyIEpvaG4mIzM5O3MgZmFybSE8XC9wPlxyXG5cclxuPHA+VGhlIG1hcmF0aG9uIGNvdXJzZSBjb25zaXN0cyBvZiBOIGNoZWNrcG9pbnRzICgzICZsdDs9IE4gJmx0Oz0gMTAwLDAwMCkgdG8gYmUgdmlzaXRlZCBpbiBzZXF1ZW5jZSwgd2hlcmUgY2hlY2twb2ludCAxIGlzIHRoZSBzdGFydGluZyBsb2NhdGlvbiBhbmQgY2hlY2twb2ludCBOIGlzIHRoZSBmaW5pc2guICZuYnNwO0Jlc3NpZSBpcyBzdXBwb3NlZCB0byB2aXNpdCBhbGwgb2YgdGhlc2UgY2hlY2twb2ludHMgb25lIGJ5IG9uZSwgYnV0IGJlaW5nIHRoZSBsYXp5IGNvdyBzaGUgaXMsIHNoZSBkZWNpZGVzIHRoYXQgc2hlIHdpbGwgc2tpcCB1cCB0byBvbmUgY2hlY2twb2ludCBpbiBvcmRlciB0byBzaG9ydGVuIGhlciB0b3RhbCBqb3VybmV5LiAmbmJzcDtTaGUgY2Fubm90IHNraXAgY2hlY2twb2ludHMgMSBvciBOLCBob3dldmVyLCBzaW5jZSB0aGF0IHdvdWxkIGJlIHRvbyBub3RpY2VhYmxlLjxcL3A+XHJcblxyXG48cD5QbGVhc2UgaGVscCBCZXNzaWUgZmluZCB0aGUgbWluaW11bSBkaXN0YW5jZSB0aGF0IHNoZSBoYXMgdG8gcnVuIGlmIHNoZSBjYW4gc2tpcCB1cCB0byBvbmUgY2hlY2twb2ludC4gJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCBzaW5jZSB0aGUgY291cnNlIGlzIHNldCBpbiBhIGRvd250b3duIGFyZWEgd2l0aCBhIGdyaWQgb2Ygc3RyZWV0cywgdGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIGNoZWNrcG9pbnRzIGF0IGxvY2F0aW9ucyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgaXMgZ2l2ZW4gYnkgfHgxLXgyfCArIHx5MS15MnwuICZuYnNwO1RoaXMgd2F5IG9mIG1lYXN1cmluZyBkaXN0YW5jZSAtLSBieSB0aGUgZGlmZmVyZW5jZSBpbiB4IHBsdXMgdGhlIGRpZmZlcmVuY2UgaW4geSAtLSBpcyBzb21ldGltZXMga25vd24gYXMgJnF1b3Q7TWFuaGF0dGFuJnF1b3Q7IGRpc3RhbmNlIGJlY2F1c2UgaXQgcmVmbGVjdHMgdGhlIGZhY3QgdGhhdCBpbiBhIGRvd250b3duIGdyaWQsIHlvdSBjYW4gdHJhdmVsIHBhcmFsbGVsIHRvIHRoZSB4IG9yIHkgYXhlcywgYnV0IHlvdSBjYW5ub3QgdHJhdmVsIGFsb25nIGEgZGlyZWN0IGxpbmUgJnF1b3Q7YXMgdGhlIGNyb3cgZmxpZXMmcXVvdDsuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBnaXZlcyB0aGUgdmFsdWUgb2YgTi48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBlYWNoIGNvbnRhaW4gdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgeCBhbmQgeSwgcmVwcmVzZW50aW5nIGEgY2hlY2twb2ludCAoLTEwMDAgJmx0Oz0geCAmbHQ7PSAxMDAwLCAtMTAwMCAmbHQ7PSB5ICZsdDs9IDEwMDApLiBUaGUgY2hlY2twb2ludHMgYXJlIGdpdmVuIGluIHRoZSBvcmRlciB0aGF0IHRoZXkgbXVzdCBiZSB2aXNpdGVkLiBOb3RlIHRoYXQgdGhlIGNvdXJzZSBtaWdodCBjcm9zcyBvdmVyIGl0c2VsZiBzZXZlcmFsIHRpbWVzLCB3aXRoIHNldmVyYWwgY2hlY2twb2ludHMgb2NjdXJyaW5nIGF0IHRoZSBzYW1lIHBoeXNpY2FsIGxvY2F0aW9uLiAmbmJzcDtXaGVuIEJlc3NpZSBza2lwcyBzdWNoIGEgY2hlY2twb2ludCwgc2hlIG9ubHkgc2tpcHMgb25lIGluc3RhbmNlIG9mIHRoZSBjaGVja3BvaW50IC0tIHNoZSBkb2VzIG5vdCBza2lwIGV2ZXJ5IGNoZWNrcG9pbnQgb2NjdXJyaW5nIGF0IHRoZSBzYW1lIGxvY2F0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBkaXN0YW5jZSB0aGF0IEJlc3NpZSBjYW4gcnVuIGJ5IHNraXBwaW5nIHVwIHRvIG9uZSBjaGVja3BvaW50LiAmbmJzcDtEb24mIzM5O3QgZm9yZ2V0IHRvIGVuZCB5b3VyIG91dHB1dCB3aXRoIGEgbmV3bGluZS4gJm5ic3A7SW4gdGhlIHNhbXBsZSBjYXNlIHNob3duIGhlcmUsIHNraXBwaW5nIHRoZSBjaGVja3BvaW50IGF0ICg4LCAzKSBsZWFkcyB0byB0aGUgbWluaW11bSB0b3RhbCBkaXN0YW5jZSBvZiAxNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=