T-net
시간 제한2초메모리 제한512 MB
직선 위에 놓인 기지국 위치와 두 종류의 안테나 반지름이 주어질 때, 모든 기지국을 연결하는 최소 반지름 합을 구하거나 불가능하면 -1을 출력합니다.
문제
T-net은 새로운 통신 회사이다. 이 회사는 도시에 기지국을 설치할 계획이다. 기지국을 설치할 위치는 이미 정해져 있다. T-net의 기지국에는 두 종류의 안테나를 쓸 수 있다. 하나는 송신 반경이 인 안테나이고, 다른 하나는 송신 반경이 인 안테나이다. 두 안테나가 서로 통신할 수 있는 조건은 둘 다 상대방의 커버리지 안에 들어가 있는 것뿐이다. 송신 반경이 작은 안테나일수록 싸다. T-net은 모든 안테나 송신 반경의 합을 비용으로 두고, 네트워크 전체를 연결된 상태로 유지하면서 그 비용을 최소로 하려고 한다. 모든 기지국은 한 직선 위에 있다. 최소 비용으로 연결된 네트워크를 구성하시오.
입력
첫째 줄에 양의 정수 , , 가 주어진다 (, ). 은 기지국의 개수이고, 와 는 위에서 정의한 송신 반경이다. 둘째 줄에는 직선 위에 있는 기지국의 서로 다른 좌표 개가 주어진다. 좌표는 직선 위의 원점을 기준으로 한 위치이며, 모두 이하의 양의 정수이다.
출력
연결된 네트워크를 구성할 수 있으면 최소 비용을 출력한다. 그렇지 않으면 -1을 출력한다.