N명의 친구들이 각자 장난감 자동차들과 트랙을 들고 석표의 집에 모였다.

각 친구는 한 종류의 무한히 많은 트랙을 갖고 있는데,

i번째 친구가 갖고 있는 트랙의 길이는 모두 i로 동일하다.

친구들은 각자 서로 다른 방에 위치하고 있는데,

각 방들을 트랙으로 이어 어느 방에서 출발하더라도 다른 모든 방들로 도달할 수 있도록 하고자 한다.

서로 다른 두 친구 a, b의 방을 도로로 연결할 때 도로의 길이는 d_a+ d_b이다.

이 때, 모든 방이 연결되도록 하기 위한 도로의 길이의 총합의 최솟값을 구하자.

[제약 조건]

1 <= N <= 100000

1 <= d_i <= 10⁹

[Subtask]

Subtask #1 (20점) : d₁= d_<2 = ... = d_n

Subtask #2 (40점) : 1 <= N <= 1000

Subtask #3 (40점) : 추가 제한 조건 없음

도로 연결 timer 1초 memory 512MB

도로 연결 1초 512MB