시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 407 137 107 40.377%

문제

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

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

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

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

입력

첫 번째 줄에 체크포인트의 수 N과 건너뛸 체크포인트의 수 K가 주어진다.

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

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

출력

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

예제 입력 1

5 2
0 0
8 3
1 1
10 -5
2 2

예제 출력 1

4

힌트

젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다.

W3sicHJvYmxlbV9pZCI6IjEwNjUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWM4XHViNzdjXHVkMWE0IDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YzdhNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE2XHVjMThjXHViNGU0XHVjNzc0IFx1YWM3NFx1YWMxNVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHVjODE2XHVjMThjXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU1YyBcdWI5YzhcdWI3N2NcdWQxYTQgXHViMzAwXHVkNjhjXHViOTdjIFx1YzVmNFx1YzVjOFx1YWNlMCwgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc1OCBcdWNkMWRcdWM1NjBcdWI5N2MgXHViYzFiXHViMjk0IFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDAgXHVjNWVkXHVjMmRjIFx1Yzc3NCBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTYwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHViNzdjXHVkMWE0IFx1Y2Y1NFx1YzJhNFx1YjI5NCBOICgzICZsdDs9IE4gJmx0Oz0gNTAwKSBcdWFjMWNcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIDFcdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjY2I0XHVkMDZjIFx1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzI5XHViYjM4XHVkNTVjIFx1ZDZjNCBOXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2NcdWM5YzAgXHViOWM4XHViNzdjXHVkMWE0XHVjNzc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVhYzhjXHVjNzNjXHViOTc4IFx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NDAgXHViOWM5XHVjMGMxIFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWI4MjQgXHVkNTU4XHViMmM4IFx1YWRjMFx1Y2MyZVx1YzU0NFx1YzgzOFx1YzExYyBcdWM5MTFcdWFjMDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOCBLIFx1YWMxY1x1Yjk3YyBcdWJhYjBcdWI3OTggXHVhYzc0XHViMTA4XHViNmYwXHViODI0IFx1ZDU1Y1x1YjJlNC4gKEsgJmx0OyBOKSBcdWIyZTgsIDFcdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNjQwIE5cdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1YWM3NFx1YjEwOFx1YjZmMFx1YmE3NCBcdWIxMDhcdWJiMzQgXHViMjA4XHVjZTU4XHVhYzAwIFx1YmNmNFx1Yzc3NFx1YjJjOCBcdWI0NTAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViMjk0IFx1YWM3NFx1YjEwOFx1YjZmMFx1YzljMCBcdWM1NGFcdWM3NDQgXHVjMGRkXHVhYzAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTZcdWMxOGMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzc0IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWNkNWNcdWIzMDAgSyBcdWFjMWMgXHVhYzc0XHViMTA4XHViNmYwXHViYTc0XHVjMTFjIFx1YjJlY1x1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0LCBcdWFjZmNcdWM1ZjAgXHVjMmI5XHVjNmQwXHVjNzc0XHVhYzAwIFx1YjJlY1x1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1YjI5NCBcdWM1YmNcdWI5YzhcdWM3N2NcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlx1Y2MzOFx1YWNlMFx1Yjg1YywgXHVjODE2XHVjMThjIFx1YjljOFx1Yjc3Y1x1ZDFhNCBcdWIzMDBcdWQ2OGNcdWIyOTQgXHVjMTFjXHVjNmI4XHVjMmRjXHViMGI0IFx1ZDU1Y1x1YmNmNVx1ZDMxMFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MjAgXHVjNjA4XHVjODE1XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVkMGRkXHVjMmRjIFx1YWM3MFx1YjlhYyhNYW5oYXR0YW4gRGlzdGFuY2UpXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgKHgxLHkxKVx1YWNmYyAoeDIseTIpIFx1YzgxMCBcdWFjMDRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IHx4MS14MnwgKyB8eTEteTJ8IFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKHx4fFx1YjI5NCBcdWM4MDhcdWIzMTNcdWFjMTIgXHVhZTMwXHVkNjM4XHViMmU0Lik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWFjNzRcdWIxMDhcdWI2ZjggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNzU4IFx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWI0NTBcdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggaVx1Yzc1OCB4IFx1Yzg4Y1x1ZDQ1YywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgeSBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuICgtMTAwMCAmbHQ7PSB4ICZsdDs9IDEwMDAsIC0xMDAwICZsdDs9IHkgJmx0Oz0gMTAwMCk8XC9wPlxyXG5cclxuPHA+XHVjY2I0XHVkMDZjIFx1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVhY2I5XHVjZTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQgLSBcdWM4MTZcdWMxOGMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzc0IFx1ZDU1YyBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4IFx1YjU0Y1x1YjI5NCBcdWFkZjggXHViYzg4XHVkNjM4XHVjNzU4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YjljYyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWJhNzAsIFx1YWRmOCBcdWM4MTBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MTZcdWMxOGMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzc0IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOCBLIFx1YWMxY1x1Yjk3YyBcdWFjNzRcdWIxMDhcdWI2ZjBcdWFjZTAgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzgxNlx1YzE4YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NzQgMlx1YmM4OFx1YzlmOCBcdWM2NDAgNFx1YmM4OFx1YzlmOCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVhYzc0XHViMTA4XHViNmY4XHVhY2JkXHVjNmIwIFx1YWNiZFx1Yjg1Y1x1YjI5NCAoMCwwKSAtJmd0OyAoMSwxKSAtJmd0OyAoMiwyKSBcdWI4NWMgNFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWIzNTQgXHVjOWU3XHVhYzhjIFx1YjJlY1x1YjliNFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDY1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hcmF0aG9uIiwiZGVzY3JpcHRpb24iOiI8cD5VbmhhcHB5IHdpdGggdGhlIHBvb3IgaGVhbHRoIG9mIGhpcyBjb3dzLCBGYXJtZXIgSm9obiBlbnJvbGxzIHRoZW0gaW4gYW4gYXNzb3J0bWVudCBvZiBkaWZmZXJlbnQgcGh5c2ljYWwgZml0bmVzcyBhY3Rpdml0aWVzLiAmbmJzcDtIaXMgcHJpemUgY293IEJlc3NpZSBpcyBlbnJvbGxlZCBpbiBhIHJ1bm5pbmcgY2xhc3MsIHdoZXJlIHNoZSBpcyBldmVudHVhbGx5IGV4cGVjdGVkIHRvIHJ1biBhIG1hcmF0aG9uIHRocm91Z2ggdGhlIGRvd250b3duIGFyZWEgb2YgdGhlIGNpdHkgbmVhciBGYXJtZXIgSm9obiYjMzk7cyBmYXJtITxcL3A+XHJcblxyXG48cD5UaGUgbWFyYXRob24gY291cnNlIGNvbnNpc3RzIG9mIE4gY2hlY2twb2ludHMgKDMgJmx0Oz0gTiAmbHQ7PSA1MDApIHRvIGJlIHZpc2l0ZWQgaW4gc2VxdWVuY2UsIHdoZXJlIGNoZWNrcG9pbnQgMSBpcyB0aGUgc3RhcnRpbmcgbG9jYXRpb24gYW5kIGNoZWNrcG9pbnQgTiBpcyB0aGUgZmluaXNoLiAmbmJzcDtCZXNzaWUgaXMgc3VwcG9zZWQgdG8gdmlzaXQgYWxsIG9mIHRoZXNlIGNoZWNrcG9pbnRzIG9uZSBieSBvbmUsIGJ1dCBiZWluZyB0aGUgbGF6eSBjb3cgc2hlIGlzLCBzaGUgZGVjaWRlcyB0aGF0IHNoZSB3aWxsIHNraXAgdXAgdG8gSyBjaGVja3BvaW50cyAoSyAmbHQ7IE4pIGluIG9yZGVyIHRvIHNob3J0ZW4gaGVyIHRvdGFsIGpvdXJuZXkuICZuYnNwO1NoZSBjYW5ub3Qgc2tpcCBjaGVja3BvaW50cyAxIG9yIE4sIGhvd2V2ZXIsIHNpbmNlIHRoYXQgd291bGQgYmUgdG9vIG5vdGljZWFibGUuPFwvcD5cclxuXHJcbjxwPlBsZWFzZSBoZWxwIEJlc3NpZSBmaW5kIHRoZSBtaW5pbXVtIGRpc3RhbmNlIHRoYXQgc2hlIGhhcyB0byBydW4gaWYgc2hlIGNhbiBza2lwIHVwIHRvIEsgY2hlY2twb2ludHMuICZuYnNwOzxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgY291cnNlIGlzIHNldCBpbiBhIGRvd250b3duIGFyZWEgd2l0aCBhIGdyaWQgb2Ygc3RyZWV0cywgdGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIGNoZWNrcG9pbnRzIGF0IGxvY2F0aW9ucyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgaXMgZ2l2ZW4gYnkgfHgxLXgyfCArIHx5MS15MnwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBnaXZlcyB0aGUgdmFsdWVzIG9mIE4gYW5kIEsuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgZWFjaCBjb250YWluIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHggYW5kIHksIHJlcHJlc2VudGluZyBhIGNoZWNrcG9pbnQgKC0xMDAwICZsdDs9IHggJmx0Oz0gMTAwMCwgLTEwMDAgJmx0Oz0geSAmbHQ7PSAxMDAwKS4gVGhlIGNoZWNrcG9pbnRzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgdGhhdCB0aGV5IG11c3QgYmUgdmlzaXRlZC4gTm90ZSB0aGF0IHRoZSBjb3Vyc2UgbWlnaHQgY3Jvc3Mgb3ZlciBpdHNlbGYgc2V2ZXJhbCB0aW1lcywgd2l0aCBzZXZlcmFsIGNoZWNrcG9pbnRzIG9jY3VycmluZyBhdCB0aGUgc2FtZSBwaHlzaWNhbCBsb2NhdGlvbi4gJm5ic3A7V2hlbiBCZXNzaWUgc2tpcHMgc3VjaCBhIGNoZWNrcG9pbnQsIHNoZSBvbmx5IHNraXBzIG9uZSBpbnN0YW5jZSBvZiB0aGUgY2hlY2twb2ludCAtLSBzaGUgZG9lcyBub3Qgc2tpcCBldmVyeSBjaGVja3BvaW50IG9jY3VycmluZyBhdCB0aGUgc2FtZSBsb2NhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gZGlzdGFuY2UgdGhhdCBCZXNzaWUgY2FuIHJ1biBieSBza2lwcGluZyB1cCB0byBLIGNoZWNrcG9pbnRzLiAmbmJzcDtJbiB0aGUgc2FtcGxlIGNhc2Ugc2hvd24gaGVyZSwgc2tpcHBpbmcgdGhlIGNoZWNrcG9pbnRzIGF0ICg4LCAzKSBhbmQgKDEwLCAtNSkgbGVhZHMgdG8gdGhlIG1pbmltdW0gdG90YWwgZGlzdGFuY2Ugb2YgNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2014-2015 Season > USACO December 2014 Contest > Silver 2번

  • 문제의 오타를 찾은 사람: Acka
  • 문제를 번역한 사람: koosaga