vito 의 여러 명의 친척은 라마피아거리에 살고 있다. 이 거리에 있는 친척을 모두 방문하고자 하는 경우 어떤 집에 머무는 것이 모든 집을 방문하는데 합이 최소가 되는 지를 구하는 것이 문제이다.

예를 들어 친척들이 2 4 6 번 집에 사는 경우

2 번집에 머무는 경우

• 4 번집에 가는 거리는 2
• 6 번집에 가는 거리는 4

6 ( 2 + 4 ).

4 번 집에 머무는 경우

• 4 번 집에서 2 번집에 가는데 거리가 2 이고
• 4 번 집에서 6 번집에 가는 경우 거리가 2 이므로

합이 4 로 최소이다.

입력

출력

입출력 예

입력

2 
2 4

출력

2

입력

3 
2 4 6

출력

4

출처: http://acm.uva.es/p/v100/10041.html