문제
철수는 체크포인트 달리기라는 경기에 출전했다. 체크포인트 달리기란 출발점에서 출발하여 길에 있는 모든 체크포인트에 최소 한 번씩 체크하고 출발점으로 돌아오는 경기이다. 출발점은 원점에 있고, 일직선으로 뻗은 길에 $N$개의 체크포인트가 있다. $i$번째 체크포인트는 좌표 $x_i$에 있다.
체크포인트 달리기에는 특별한 규칙이 있는데, 출발점에서 출발하여 출발점으로 돌아오기 전까지 최대 $K$개의 체크포인트에만 체크할 수 있다. 예를 들어 $K$가 3ドル$이라면, 출발점에서 출발하여 3ドル$개의 체크포인트를 체크하고, 출발점으로 돌아온 뒤, 다시 다른 체크포인트를 향해 달려가야 한다. 체크포인트를 체크하지 않고 지나칠 수도 있다.
철수가 이동 거리를 최소화하면서 모든 체크포인트를 체크할 수 있게 도와주자.
출력
철수가 이동 거리를 최소화하면서 모든 체크포인트를 체크할 때, 그 이동 거리를 출력한다.
제한
- 주어지는 모든 수는 정수이다.
- 1ドル \leq N \leq 200\ 000$
- 1ドル \leq K \leq N$
- $-10^9 \leq x_i \leq 10^9$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 30 | $K = 1$
|
| 2 | 70 | 추가 제약 조건이 없음.
|
W3sicHJvYmxlbV9pZCI6IjI5ODkxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4IFx1YjJlY1x1YjlhY1x1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjY2EwXHVjMjE4XHViMjk0IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOCBcdWIyZWNcdWI5YWNcdWFlMzBcdWI3N2NcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNWQwIFx1Y2Q5Y1x1YzgwNFx1ZDU4OFx1YjJlNC4gXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4IFx1YjJlY1x1YjlhY1x1YWUzMFx1Yjc4MCBcdWNkOWNcdWJjMWNcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1YWUzOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzVkMCBcdWNkNWNcdWMxOGMgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWNjYjRcdWQwNmNcdWQ1NThcdWFjZTAgXHVjZDljXHViYzFjXHVjODEwXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NzRcdWIyZTQuIFx1Y2Q5Y1x1YmMxY1x1YzgxMFx1Yzc0MCBcdWM2ZDBcdWM4MTBcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViZWQ3XHVjNzQwIFx1YWUzOFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVhYzAwIFx1Yzc4OFx1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YjI5NCBcdWM4OGNcdWQ0NWMgJHhfaSRcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggXHViMmVjXHViOWFjXHVhZTMwXHVjNWQwXHViMjk0IFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWFkZGNcdWNlNTlcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwLCBcdWNkOWNcdWJjMWNcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YmMxY1x1YzgxMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWFlMzAgXHVjODA0XHVhZTRjXHVjOWMwIFx1Y2Q1Y1x1YjMwMCAkSyRcdWFjMWNcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHViOWNjIFx1Y2NiNFx1ZDA2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0ICRLJFx1YWMwMCAkMyRcdWM3NzRcdWI3N2NcdWJhNzQsIFx1Y2Q5Y1x1YmMxY1x1YzgxMFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgJDMkXHVhYzFjXHVjNzU4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWNjYjRcdWQwNmNcdWQ1NThcdWFjZTAsIFx1Y2Q5Y1x1YmMxY1x1YzgxMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjggXHViNGE0LCBcdWIyZTRcdWMyZGMgXHViMmU0XHViOTc4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWQ1YTVcdWQ1NzQgXHViMmVjXHViODI0XHVhYzAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1Y2NiNFx1ZDA2Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHVjOWMwXHViMDk4XHVjZTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhMFx1YzIxOFx1YWMwMCBcdWM3NzRcdWIzZDkgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YmE3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1Y2NiNFx1ZDA2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVhY2ZjIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVjY2I0XHVkMDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOCAkSyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgJE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjNzA0XHVjZTU4ICR4X2kkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYTBcdWMyMThcdWFjMDAgXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWJhNzRcdWMxMWMgXHViYWE4XHViNGUwIFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWNjYjRcdWQwNmNcdWQ1NjAgXHViNTRjLCBcdWFkZjggXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgTiBcXGxlcSAyMDBcXCAwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIEsgXFxsZXEgTiQ8XC9saT5cclxuXHQ8bGk+JC0xMF45IFxcbGVxIHhfaSBcXGxlcSAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kSyA9IDEkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWM3NGMuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk4OTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSYWNlIHdpdGggQ2hlY2twb2ludHMiLCJkZXNjcmlwdGlvbiI6IjxwPkFsYmVydCBpcyBwYXJ0aWNpcGF0aW5nIGluIHRoZSZuYnNwOyZxdW90O1JhY2Ugd2l0aCBDaGVja3BvaW50cy4mcXVvdDsgSW4gdGhlIFJhY2Ugd2l0aCBDaGVja3BvaW50cywgYSBydW5uZXIgbXVzdCBzdGFydCZuYnNwO2Zyb20gYSBkZXNpZ25hdGVkIHN0YXJ0aW5nIHBvaW50LCBjaGVjayBpbiBhdCZuYnNwO2V2ZXJ5IGNoZWNrcG9pbnQgYXQgbGVhc3Qgb25jZSwgYW5kIHRoZW4gcmV0dXJuJm5ic3A7dG8gdGhlIHN0YXJ0aW5nIHBvaW50LiBUaGUgc3RhcnRpbmcgcG9pbnQgaXMgbG9jYXRlZCBhdCB0aGUgb3JpZ2luLCBhbmQgdGhlcmUgYXJlICROJCBjaGVja3BvaW50cyBhbG9uZyBhIHN0cmFpZ2h0IGxpbmUuIFRoZSAkaSQtdGggY2hlY2twb2ludCBpcyBsb2NhdGVkIGF0IGNvb3JkaW5hdGUgJHhfaSQuPFwvcD5cclxuXHJcbjxwPlRoZSBSYWNlIGhhcyBzcGVjaWFsIHJ1bGVzIHdoZXJlIHRoZSBydW5uZXIgY2FuIGNoZWNrIGluIGF0IG1vc3QgJEskIGNoZWNrcG9pbnRzIGFmdGVyIGxlYXZpbmcgdGhlIHN0YXJ0aW5nIHBvaW50IGFuZCBiZWZvcmUgcmV0dXJuaW5nIHRvIGl0LiBGb3IgaW5zdGFuY2UsIGlmICRLJCBpcyAkMyQsIHRoZW4gdGhlIHJ1bm5lciBjYW4gbGVhdmUgdGhlIHN0YXJ0aW5nIHBvaW50IHRvIGNoZWNrIGluIGF0ICQzJCBjaGVja3BvaW50cywgcmV0dXJuIHRvIHRoZSBzdGFydGluZyBwb2ludCwgYW5kIHRoZW4gcnVuIHRvIGNoZWNrIG90aGVyIGNoZWNrcG9pbnRzLiBUaGUgcnVubmVyIGlzIGFsbG93ZWQgdG8gc2tpcCBhIGNoZWNrcG9pbnQgd2l0aG91dCBjaGVja2luZyBpdC48XC9wPlxyXG5cclxuPHA+TGV0IHVzIGhlbHAgQWxiZXJ0IG1pbmltaXplIHRoZSB0b3RhbCBkaXN0YW5jZSB0byBiZSBydW4gd2hpbGUgY2hlY2tpbmcgaW4gYXQgZXZlcnkgY2hlY2twb2ludC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiB0aGUgbnVtYmVyIG9mIGNoZWNrcG9pbnRzLCAkTiQsIGFuZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgY2hlY2twb2ludHMgdGhhdCBjYW4gY2hlY2tlZCBpbiBhdCBvbmNlLCAkSyQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgJE4kIGxpbmVzIHdpbGwgY29udGFpbiAkeF9pJCwgdGhlIGNvb3JkaW5hdGUgb2YgdGhlICRpJC10aCBjaGVja3BvaW50LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBkaXN0YW5jZSB0aGF0IEFsYmVydCBtdXN0IHJ1biB3aGlsZSBjaGVja2luZyBpbiBhdCBhbGwgY2hlY2twb2ludHMgYXMgaGUgbWluaW1pemVzIGl0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+QWxsIG51bWJlcnMgZ2l2ZW4gaW4gaW5wdXQgd2lsbCBiZSBpbnRlZ2Vycy48XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgTiBcXGxlcSAyMDBcXCAwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIEsgXFxsZXEgTiQ8XC9saT5cclxuXHQ8bGk+JC0xMF45IFxcbGVxIHhfaSBcXGxlcSAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kSyA9IDEkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5ObyBhZGRpdGlvbmFsIHJlc3RyaWN0aW9ucyBvbiBpbnB1dC48XC9wPlxyXG4ifV0=